I think for starting out RedHat is as good as any other distro, and in fact I am somewhat partial to RedHat.
But you have the right idea with the CLI. Learn as much as you can on the commandline, and stay away from the GUI tools if at all possible. I'm not saying don't install the GUI, you can do that and not hinder yourself, just use terminal windows and stick to that.
Once you have gotten the basics of *nix down then start trying every distro out there. That way you can get a general idea of how they all differ and you can pick the one that you feel suits your style the best. Myself, I use Gentoo Linux and Open BSD here at home. Out of all the *nix's I have tried (quite a few) those are my personal favs.
And one last thing: Moved to *nix & *nix Security