Personally I find most video game characters have too much baggage to form a stable relationship with (saving the world, avenging parent's deaths, killing large demons, etc) but my friends sat next to me say the following:
Tim - Rydia from FFIV "cos she's hot". Not picky huh? and he's available ladies ;P.
Aaron - Misty from Pokemon "cos watery redheads are much better than fiery ones".