Incans can get the earliest conquest going with their Quechuas. If you are playing on Monarch or below, build 4-5 and go kill your nearest neighbor before 2000 BC. They aren't exactly super moblie, but they are cheap and get 100% versus Archers.
My favorite, though, is the Persian Immortal. They replace the Chariot in this game instead of the swordsman like in Civ III. They are fast and awesome for early conquest. The only downside is that you need horses. Egypt is quite similar with War Chariots.
The Roman Praetorians are really strong too, but I haven't used them yet.
For overall warmongering, I'd have to vote for Japan. Organized and Aggressive are probably the best traits for warmongering (in Vanilla). Cheap courthouses, free promotions, and Samurai are nice. Organized is one of the strongest traits as it is.
EDIT: 69th post, yeah baby!
Ignore the Japan thing. I didn't see you that you have Warlords. Although, they can still be good warmongers.