[Eomer of the Rohirrim]

The guards weren't allowed to let any random through without questioning them. Gandalf couldn't have expected them to say "Alright, if he's a Man you can enter."

Disregarding the point that the soldiers had already heard of Halflings, Gandalf could surely have said something like "This is Peregrin Took, a Halfling from the North, whom your Lord would be most eager to meet."

Then he could have waltzed into the City immediately.