In the meantime, I’ve gone for a) low cache time – 60 minutes, plenty enough to have good performance though, and b) disable cache for logged in users only. This seems to be a satisfactory solution to me.
I also found, under heavy load, that Super/Total cache didn’t help a great deal, while Quick Cache had a massive impact. YMMV though of course.
Regarding all the relative times (x minutes ago, etc), the best solution would probably be to put absolute times into all those places, along with some javascript to turn it into a friendly relative time at the client end.
As well as being cache-friendly, this solution would allow the possibility of locally updating, so if you switch to another tab in the browser and switch back a few hours later, the “1 minute ago” can change to “3 hours ago”.