If you want to go that way, I think the rpms should be installed in a directory named something similar to /var/usr/$USER.
The entire hierarchy under /var/usr should be writable only by some system user, installing packages should be done by a program that is suid to that user.
If two users installs the same package, then the files can be hardlinked into both users' directories. The program to perform the install can also manage some sort of quotas.
Obviously it should not be possible to install any suid or sgid executables or any device inodes. Running the install as a non-root user guarantees part of that.
There is a problem with how programs find their files. They would either need to be modified to use the USER environment variable, or you would need a symlink somewhere that magically points to /var/usr/$USER and then use paths through that. (There are already symlinks in /proc that magically changes depending on which process access them, so adding another magical symlink doesn't seem too far fetched). Of course it may still be problematic that an rpm can either be installed in the normal location by root or a different location by somebody else. Could be worked around by building two versions of each rpm.
The only reason I suggest a directory name depending on the user is, that one user installing a program shouldn't cause that program to show up in another user's path. Each user would have /var/usr/$USER/bin in their path, and only see programs they want to see there.
If some files are accessed by a path that is determined at compile time, maybe those should be put into a common directory instead. That would avoid most of the user dependent path requirements. Say user1 installs app with a binary named app and a library named libapp.so.1, then each file of the two files could be hardlinked in two locations.
And user1 would access /var/usr/user1/bin/app from the path which would then use /var/usr/common/lib/libapp.so.1. The common directories shouldn't be in any path, but if you want to specify the absolute path to for example an executable you would use the one in /var/usr/common/bin/app.
I may have missed some details that would need to be figured out, but I'm pretty sure it can be made to work within the normal unix security model, if anybody wants to do the work.