If you haven't specifically flashed the stock deodexed rom, it's odexed. You'll need to flash the stock deodexed rom to be able to theme. The themes will need to be made specifically for stock, Sense 2.1/3.0, CM7/AOSP and MIUI themes won't work.
If you want more themes, you'll be better off flashing a custom rom. I'm not sure about the availability of Sense themes, but CM7 and MIUI have theming built in. These are both AOSP roms, they're not Sense which is what you're used to. MIUI is my personal favorite, and definitely the most themable.
You can always make a nandroid backup and try out different roms/themes. If you don't like what you flash, just restore your backup or keep flashing until you find something you like.
Sent from my Evo + MIUI using Tapatalk!