Currently almost all Linux programs hardcode their installation path into their binary. This means that they must be installed to the location spesified at compile time or they will break. This is an unnecessary historical burden.
In comparison Windows and OSX binaries can be installed anywhere and they just work. Linux should be able to do the same.
Currently users add unofficial repositories which can destabilise the system. With relocatable binaries these programs could be installed separate from the main system (for example to /opt/reponame). In case of trouble they can be easily disabled returning the system to a know good condition.
Developers can test experimental sofware easier. Daily snapshots of a package can be installed in parallel without any additional effort placed on the packager. If required a tester can even keep every daily build of a binary on his machine for easy regression testing.
Allows for easy installation of per-user software on machines where the user is not given root access (such as in the workplace). The user simply installs packages to a spesified location in his home directory. In security conscious environments this can be disabled. (note that users can do this already if they are willing to compile sources themselves).
Developers can run their programs directly from the build tree without issuing a prefix, make install, symlinks or other hacks. This makes the development cycle faster.
Suppose a user wants to run two instances of some program (say Foobar) in parallel. Currently this has to be done either through virtualization, chroot or compiling your own to /usr/local (which loses security updates and all other advantages of a package system). With relocatable binaries you could effectively just do aptitude --prefix=/some/other/place install foobar.
Executable files should work with minimal fuss. There may be some issues with resolving symbols and paths on complicated setups. This may require changes to the dynamic linker. Basic setups should work without any problems.
A method should be added which allows any executable or library to ask its current full filesystem path. For executables this is roughly equivalent to reading the dirname from /proc/self/exe. Some choices:
A new syscall/libc addition/similar called (for example) getlocation(), which returns a string containing the requested path of the file (such as /usr/lib/libfoo.so) that contains the code that issued the call. This seems to be the most straightforward solution.
The system is responsible for maintaining an environment variable (say $ORIGIN as in Solaris) that points to the file. Downsides: possibly complex, does not work for dynamic libraries.
Using binreloc on every package. Downsides: duplicates code, Linux-only implementation, a bit hacky.
1) design and implement a working solution
2) discuss with other distros, BSDs and other unices and try to reach a joint standard
3) convince upstream developers to update their programs to take advantage of the new functionality
4) enjoy a system liberated of yet another legacy hindrance