I had rooted my Desire HD and used CM, which I loved much more than sense since it made the phone faster, I could do whatever I wanted with it etc. I'm 98% sure I will want to root and use CM on my new phone as well, so please don't name phones that are a total bitch to get fully rooted. It was a little bit of work to root my HD, but following a guide from top to bottom got me through it.. Thank god you only have to do it once.
Anyways, I do use the camera quite a lot on my phones so an OK camera is a big plus. I also fiddle alot with my phones during the day, so good batterytime is a huge plus... And if the battery is easy to take out and put in that is also a plus so I can carry around extra batteries which I am used to from having a Desire HD which burned of batterytime like crazy.
Good GPS signal is also nice to have as I suck at getting around places I don't know. :P
Hmmm... What else is there to say.. I dunno. Maybe this is enough for now