Honestly I was thinking of making her the paladin tank and you could be a complimenting healer or CC.
High elf women are about as "pretty" as it gets. If she wants to be a bit more hippy,
half elven women have "flared" plate boots.
If you made a shaman, cleric, enc, bard, or necro, you guys would have a pretty potent duo and a great start for a group.
As a paladin, she could do the tanking (which is mostly just pick a target and beat it to death, cast Flash of Light and Stun on it occasionally (not hard), while you could do the pulling with lull (as a enc, cler, or bard) and support with heals, buffs, slows, etc. (as a sham, cler, enc, bard). With this being her first character, let her play the easier role while you play a class that can fill in the gaps. And if she can learn to become a good tank, then you will really be set!