Netbeans has a pretty good UI for gdb, and it also has the best graphical source control client for Linux. I think they purposely try to rip off VS. It also has some refactoring capabilities for C++.
Same goes for eclipse (although I personally prefer netbeans)
Nost importantly, there are some scripts you can install that will let you view inside STL containers in gdb.
I'm actually a VS junkie myself... If I can, I just use C++11 or boost, and debug as much as possible in Visual studio, then run on Linux as late as possible.
And +1 for valgrind. It's not my "go-to" debugger, but there's nothing quite like it for finding memory leaks.