My most recent experience on Android was with a Samsung Galaxy S4, and my biggest recommendation is to immediately root the thing and figure out how to rip out all the useless crap that comes pre-installed on the phone.
Once I jettisoned the voluminous pile o' lameness that came with it, it turned out to be a decent phone.
That's the reason I never recommend Samsung phones. I can't stand TouchWiz, it's just the worst.
Fortunately the two phones discussed in this thread so far (the Moto X and the OnePlus) won't have that issue. For the most part they're pretty close to stock, especially the Moto.