Is there any kind of reasonable GUI for yum yet? A lot of these problems wouldn't matter if the "session" was longer, and it was only doing all of this parsing once at startup, letting you do multiple queries and installs without it needing to start over from scratch each time. I thought Ximian Red Carpet was fantastic and I really miss it.
The fedoranews.org server where it is hosted is down as I write this, but there is GYUM - I think it's new and I haven't tried it yet, so I can't vouch it:
http://www.fedoraforum.org/forum/showthread.php?t=29014
Steven Garrity