It's a mix of several problems that you are seeing. I'll recap, not just for you, but for someone who finds this through search.
#1 -- Any contacts that are synced with gmail are downsized to 96x96. This can be demonstrated by uploading a nice hi res photo to a google contact, then syncing twice. The first sync will send the contact photo TO your gmail contacts the second will bring back the downsized version to your phone. On anything made after 2008 it looks HORRIBLE. There is a work-around by linking local (phone) contacts which keep the high resolution picture on the phone itself, which leads to...
**Earlier EVOs had either a 250x250 or 200x200 local contact photo allowance. This looked great there, because the screens were much lower resolution.
#2--As of ICS the local contact photo is maxed at 256x256. Though this is an improvement from the 96x96, it still looks pixilated on a 720 res screen. So doing a local contact version improves the situation from HORRIBLE to merely BAD
This has been addressed in Jellybean, where the contact resolution has been bumped up to 720x720. Fortunately, this device is almost guaranteed to get the update (unless HTC wants a small riot), so it's a waiting game...
Hope this helps, if so, let me know via thanks or reply.