Debian is always quite nice, and since Ubuntu came so popular, finding packages isn’t a problem. (Ubuntu is just a special flavour of Debian)
The upside is you could still use Gnome as a GUI (prolly remote/over the network) if you feel like it, but of course everything can be done on the console as well.
I guess though, that especially if you are new to Linux, an X-Window system comes in handy.