Of the choices presented, I do think the Warlord is among the best.
Battlesmith, Cavalier, Herald, Noble, Strategist, Tactition and Warmonger are right out.
Commander isn't quite right, I think, but I can't quite put my finger on it.
Marshal could work, but I prefer Warlord. Same for Warmaster. I could also go with Captain, since that sounds somewhat dashing.
"Oh Warlord, my Warlord!"
And sure, Warlord sounds a bit too prestigious for 1st-level, but so does Paladin in my opinion. And it's not like you could start your career as Warmaster, Captain or Marshal, either.
"Wardude, where's my siege engine?"
Negative connotations aren't exclusive to warlords, either. What about "sorcerers" or "warlocks". Most of the time I heard those, it was part of the name of some evil bastard.