Assuming you are dead set on HIE or HEF, pick Tunare, simply for the
Nature's Defender. One of the best looking weapon graphics ever, and a good sword to boot.
Then the next decision is based on looks. Here are the Velious armor textures for
Half-Elf and
High Elf. High Elf is better in my opinion, but you can make your own conclusions.
From a min/max perspective, HEF get slightly better base stats, but both are inferior to DWF. ERU bring up the rear in paladin starting stats.
Good luck!