Currently, there are only two good graphical ways to find and install a package. Synaptic and Add/Remove.
Synaptic is oriented towards more experienced users, for you've got to know which package you're looking for, which means you've got to have a basic/medium knowledge in the packages system.

Add/remove, however, is more user-friendly, but currently too simple. First, there should be some way to separate GNOME programs from KDE or XFCE programs. A basic user would like to have its desktop as coherent as possible, which means no GTK programs in his Qt environnement, or no Qt programs in his GTK environment (I know this is totally possible, and that many people do it, but basically, a non experienced user don't want his desktop look like a patchwork).

Second, the search bar should allow to search by package names, package description, or both. This is a basic feature that helps a lot to narrow down the search results. Synaptic already has it, but I think it's too much a power tool for basic users.

Empowering a little the Add/remove tool would allow beginners to really enjoy, and take fully advantage of, our efficient way of installing programs.