The open-source Google CPU profiler is really nice: not only does it have nice output (see the call graph image on that page) but it's also low-overhead -- you don't need to recompile your code (only relink) to use it. And since it's open source, you can even use it for your own projects.
We even have the libraries at work set up so you can connect to any running server and ask "why are you going slow? gimme a profile". 10% speedup on a single computer is nice, but if you're running your code on a thousand computers a 10% speed up is like 100 more servers you get for free.
Sysprof is a sampling CPU profiler that uses a Linux kernel module to profile the entire system, not just a single application. Sysprof handles shared libraries and applications do not need to be recompiled. In fact they don't even have to be restarted.