Yum seems a little faster than apt-get/aptitude to me. Do you have the yum cache enabled? Yum normally downloads its package lists for every command, but you can make it cache the package list like apt-get does.

Even using the cache it's annoyingly slow compared to Arch's pacman. Various repoquery commands take near a minute to run whereas pacman is instantaneous. I'd guess the Python and SQLite approach are to blame.