Hmmm...
Chinese water dragon: about average on the "cool" factor, decent-sized lizard, lots of personality
Tokay gecko: mean as heck, but has nice colors and makes a decent display pet
Leopard gecko: boring, mundane, simplistic, commonplace....basically, everyone and their brother has one...think outside the box
Savannah monitor: big, needs a lot of space, can be cranky, but if fed right and handled enough, can be pretty awesome
I vote for the Chinese water dragon. Both species of gecko are old news IMO, and the monitor is a pretty big undertaking (emphasis on BIG). Not my first suggestion for a newbie herper.
Are snakes out of the question?