A few other things to consider:
-Are all the guards Paladins, or is the guard headed by Paladins with NPCs as the rank and file guards (so, likely warriors and experts for a typical beat, with the officers as Paladins). Unless your world is one where nearly everyone has levels in a PC class, I think the second is more likely - your beat cops are 1st or 2nd level warriors, and the Paladins are the officers and SWAT. The warriors are still going to mostly follow the same code as the Paladins - lawful good, stay out of trouble, religious, etc. - but they aren't special enough to get all the goodies a Paladin does. It also means you can have some good old police corruption, always nice if your players are spending time in a city.
-Is the city a theocracy, or part of one? So, do the Paladins serve as city guards because their religion rules the city, or just because their religion is popular in that city and the feel a moral obligation?
-Particularly if the city is *not* a theocracy, are there other religions in the city, and how good are relations between the other religions and whatever church the Paladins belong to? Will the paladins, believing members of the other religion to be heretics or infidels, crack down on them and ignore minor things from members of their own religion? Or do they strive to play things 100% fair?
Some general stuff:
In addition to the good suggestions SelcSilverhand made, I'd suggest a few other things:
Equipment:
-Wear light armor for most things. A chain shirt and a light shield is still more protection than your average citizen, but it doesn't prevent you from chasing down a criminal. Masterwork reduces the ACP, important if you need to climb a ladder or charge through debris.
-Grab the heavier armor for raids on criminal hideouts and such - SWAT-team things. Still have some lightly armored people ready to chase down runners, though.
-Longsword might be classic, but grab a flail. The bonuses to Disarm and Trip dovetail nicely with SelcSilverhand's suggestions.
Feats:
-Run. Great for chasing down fleeing criminals. Without it, your Paladins can't even hope to keep up with an unarmored pickpocket if they're wearing medium or heavy armor. And if they're wearing light armor, the Paladins can actually outrun most people, making it easy to catch fleeing criminals.
-Alertness and Negotiator are both decent choices for a guard. Spot trouble, and learn how to diffuse it. Investigator is another option.
-Improved Initiative. If you expect criminals to run rather than fight, this lets you cut off their escape route.