OP,
you forgot to mention which of the following scenaries applies to your budget:
A) phone only. no contract agreements, no contract discounts.
B) new phone & contract. in the us typically 2 years, hefty discount on new phone.
C)refurbished phone. pick with plan, or without plan.
----
i'm not sure how things work in NZ but with my contract renewal i got a new android phone for $99 in store. to purchase outright without a plan was $600.
i'm currently using an htc incredible and so far the only issue i've found was that haptic feedback stops working at times which from what i've read, i might just have a dud. everything else has been great.
i was not at all impressed with the others on display. the physical keyboard on some wasn't all that great and the onscreen keyboard on some had excessive lag. if you have a local cellphone store you might want to play around with them for a bit.
a few things about the market in general:
amoled screens like mine aren't the best in direct sunlight. i've heard about a new screen type being implemented in some newer phones but i'm not sure what the name of it was. supposedly it offers better viewing in direct sunlight.
there is a new snapdragon cpu soon to be released (look it up in tomshardware articles, they did one a few weeks ago) that is more powerful then gen1 and uses quite a bit less power too! might be a real battery saver.