well, i got Run 3 and then leveled to 62 before i hit the AAs hard and am satisfied that that was a solid route. the first defensive AAs are what, level 56/59 required? and those avoidance and mitigation lines are the meat and potatoes of the warrior class.
but unlike you i was all about grouping, and i never had much patience for soloing and therefore can't recommend where next for you to solo :( i found the exp (and the conversation =P ) much more rewarding when grouping with others. but since you prefer soloing i'd recommend some offensive AA's to up your dps (Ferocity, Flurry, Double Riposte) having them will also up your aggro which will of course also come in cool if/when you group. and since when you solo it's essentially your hp bar against the mob's - those defensive AAs (in a few levels) will help you stay alive longer to kill your target.
as far as leveling to 75 before starting AAs - if you've got gear waiting for you to get the levels, you've got a chance. if not, id recommend stopping at 62 or 65 to catch up on some AAs, 100-200 if you can, and gearing up at 65/70/71. because a 75 WAR with no AAs would be like a cleric with a 500mp manapool, near impossible to solo anything OR get a group :(
playing a WAR is remarkably slow and steady going, but in a few more levels you'll be getting some game-changing disciplines (Furious & Mighty Strike for example) and things'll start looking up! have fun!