>And finally there's this "aptitude" thing; I still don't understand why it exists and how it's different from regular apt.

Aptitude is a APT frontend that solves exactly the problem you mentioned; no more `apt-cache search` nor `apt-file`, it's all just `aptitude`. Plus a little bit of dependencies tracking (which I think apt has it available for a while already). aptitude is exactly what apt should be, IMHO.