Some more thoughts on possibly hardening more by default - comments and corrections very welcome.
(I'll call "mutating ASLR" a setup where the addresses change frequently, and "static ASLR" a setup where the addresses change only sometimes but differ between systems.)
* Servers that accept outside connections definitely should have mutating ASLR (attackers can make millions of connection attempts and outguess static ASLR). So PIE and prelink unused or ineffective (== current policy).
* Outguessing ASLR is actually more not that easy, if you guess wrong, the server very likely crashes. On many servers, that effectively ends the attack (but see https://fedorahosted.org/fpc/ticket/191
* Note that this is all made less effective by the practice of having a single daemon process that runs for months - AFAIK openssh is one of the very few exceptions that actually takes full advantage of PIE.
* For unprivileged applications that don't use the network (e.g. evince), mutating ASLR is not really useful. Sure, I can craft a a PDF exploit and convince the user to open it, but the user will not open the file a million times for me. Static ASLR is still useful because it prevents creating a single exploit that works on all systems.
* For applications that use the network as clients to mostly trusted servers or servers with limited functionality (e.g. chat, photo albums, IRC clients), mutating ASLR protects against attacks by the server to some extent, but is less necessary than for servers; million of requests that impact the UI would be definitely noticed by the user. (There might be a million server-originated requests that aren't visible in the UI, but would also likely crash the client and terminate the attack.)
* Applications like Firefox, that connect to many untrusted parties and are effectively controlled by them (even within a restricted sandbox), mutating ASLR is very useful.
With the current setup, we get "mutating ASLR" when compiled as PIE, and only partial "static ASLR" when not compiled as PIE (because the executable is static).
Based on the above I'm not so concerned about the prelink effect of making ASLR "static" - I'm more worried about the fact that executables are not randomized at all. So, would it perhaps make sense (and would it be possible) to build all executables as PIE, but continue to have two classes of builds, with "hardened builds" randomized on every start and ignoring prelink, and "nonhardened builds" prelinked every 14 days, to get complete "static ASLR" and still reduce startup latency?