Wanted: Suggestions for a New Mobile

It has been two years since I have been using the Nokia E71. (My phone previous to that was the first generation of the Apple iPhone.) So, any suggestions on what to buy next? I would actually be keen to try out an Android phone, but am open to smartphone suggestions from across the board.

Just for the record, my previous five phones have been (in reverse chronological order): Nokia E71, Apple iPhone,  Nokia N80, Nokia 6630 and Nokia 6600.