I use dreamhost which sells domains at 10 bucks with automatic private registration. But dreamhost only sells .com, .net, and .us I believe. For the others I use name.com

Honestly I haven't done enough research, but I completely agree with the OP. I'd rather pay double than to have to sift through godaddys utter bullshit of a UI.