I want to see the Gorns. The Star Trek movie never really had an "Alien" looking antagonistic race for the Enterprise crew.
I agree, the Gorn or the Tholians would be cool. The Gorn could be made to look pretty badass with movie budget CGI if we moved *slightly* away from them just being overgrown lizards. Likewise the Tholians have the potential to be a pretty scary foe if done correctly.
Perhaps one of these races in conjunction with Khan, two seperate bad guys in one film?
Gorn or Tholians! Better yet, Gorn and Tholians!
Actually, wait. If they fight the Gorn, we will have to sit through months of the moral perfectionists telling us how Star trek has lost all sense of right and wrong, because in TOS the Federation never went to war with the Gorn.

Seriously, though, they're starting from the beginning. The sky's the limit here. They can do anything now. I just don't think revisiting Khan is a good idea. Besides, Nero was very Khan-like, anyway, in his Captain Ahab style quest for revenge against the person he believes is responsible for the death of his wife. So how about not doing back-to-back movies about a crazed madman out to destroy the galaxy?