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.