I went through the trouble of getting these nice looking boots for my Horde bank alt with the intention of putting Minor Speed on them. Unfortunately, the enchant won't apply, probably because they're still classified as starter items. Argh!
edit: I used Simple Linen Boots as an alternative for enchanting. They're the same model as Recruit's Boots, except in a bluish-gray color.
I've submitted a screenshot of my bank alt wearing these boots... get a tux made and you're in business. Even if you're not a bank alt, anyone wearing a tux needs a nice pair of boots and these by far look the best. Cost? 30c... to mail the recruits boots from the newly created toon to yours.
The other items in the outfit are Recruit's Pants, and Recruit's Shirt.
Human and Gnome Warriors also start with Worn Wooden Shield, and Worn Shortsword.
Dwarf Warriors also start with Worn Battleaxe.