By all means, do the Vice-Presidents. Until you know Richard M. Nixon from Richard M. Johnson and Cactus Jack Garner from Sunny Jim Sherman, you can’t be certified as a nerd.
I’ll second the Animaniacs “Nations of the World” song. I’m going to memorize that one for fun one of these days. I like memorizing favorite song lyrics/poetry myself, because it’s artistically rewarding and can be really impressive too. I once nearly picked up a guy (at my bachleorette party, so I wasn’t really looking…) because we discovered that we both knew all the words to “We Didn’t Start the Fire.” (I have since I was about 13, long before I knew what it all meant, too!)
Wikipedia has a “List of lists,” also: http://en.wikipedia.org/wiki/List_of_lists