Odexed roms are smaller, and have a faster boot time. The only problem with them is they're harder to theme / mod.
De-odexed roms are slightly larger, and boot slower, but you cam mod the crap put of em. Just about all themed roms are deodexed. But not all. We're starting to see some odexed roms with themeing included. Not really sure how this is accomplished, but I'm still learning the ropes of modding.