You can always go to an Army/Navy surplice store and find a good pair of combat boots. They're not pretty, but they're black and functional, and they do come in widths (if you are willing to look really hard for narrows like I wear). Also, they'll shine up kind of dressy of rough up kind of . . .un-dressy.

They're not exacty cheap, but compared to name brand stuff, they're a steal. And they'll last forever.