Aptitude handles package removal, especially orphaned dependencies much better. I think it's now included in the Debian base system, so there's very little reason to prefer apt.

I actually use apt-get because I like to keep my system with the least amount of packages installed. I don't need any of the "recommended" packages, and if I do I'd install them manually.

Also, I usually use deborphan to find orphaned packages and remove them, if apt-get autoremove didn't find them.

Recommends are handled the same way by both tools nowadays. There are configuration options and flags to switch them off it you prefer.

You probably already know this, but apt-get defaults to installing recommended packages since Debian Lenny. Ubuntu may have been doing it for longer. To disable this, you have to set 'APT::Install-Recommends "false";' in apt.conf

I tried switching to aptitude, but the fact that its search defaults to OR for terms rather than AND made it completely unusable.

I guess I could keep using apt-cache for searching and aptitude for installation/removal though.

What? Its search is a regex, plain and simple.