A few thoughts
Similarly, all packages could include a "packagename-setup" tool that can be called *after* installation
How about this gets defined in the rpm as to what the config program is, and even the files that are used to store the config (especially useful for those programs that don't have config programs, and probably don't need one). This lets the user either fire up the config tool manually, or fire up rpm which fires up the config tool. Not sure of what the config tool or config files are for a package? Run an rpm query that'll tell you.
0. We DONT want the packaging system to be interactive
I agree and disagree. What we want is a package manager that can be interactive WHEN we want it to be, and not otherwise. Having such info available through rpm like the config program and config files makes this easy. In fact, a full installer could be simply a script that installs rpms and then runs the install script/prog provided after it's been installed. This is one point I like, as RH's installer never seems to be bug-free enough to cope with a particular way I've customised a system. *grin*
Also, you could always break your package into sections, breaking the config into a seperate rpm. You can even pre-package a number of different config types in seperate packages, which can fill common set-ups. Provide some that assume stuff, some that don't. In some make it all completely auto, in some don't. Give the user the option which to install. This is not ALWAYS the best method though, but it's something you can easily do now.
And I agree that .deb's need for upgrades to be babysat is... not optimul.
Thats the best bit about something like this config stuff. Allowing the package manager to control it means that this can all be done at the end, after the packages have been installed, or at least in some suitable order.
4. Another thing which this article does not address is uninstall.
This is a very hairy area. How to you guarantee things such as what you have installed haven't modified everything else ONCE you've done something else to the system. Sure you can roll-back (UGH!), but that takes you back to where you were just before you installed that package - which was 13 packages ago? Uninstall must be handled really well, but it'll take a lot of work. Till then, we have to rely on packages uninstalling their crap, and other packages not putting crap where they shouldn't. Not nice, I know.
Now this isn't aimed to be a answer to everything raised, but any suggestion can help. RPM needs work, yes, but like many GPL'd projects, it's still evolving. Get in and help if you can. If you can't, suggest ideas, help document it, test it. Don't just sit idle and complain.
Personally my biggest gripe is the way most config tools are written, wether they be linuxconf, yast, or even the one that comes with samba. They blow away huge parts of your config, and/or totally strip it of comments. In many cases, some of this can be attributed to the way many config files are structured (in most cases, they aren't structured at all). A little bit more regulation in these matters would be nice to see. You have to have exceptions to some cases though, as no format will handle every case - package managers included.