Tremulous and Cube are non-free, tremulous only in data and Cube in code as well (you cannot play on-line with the public code AFAIK).
I have never tried OpenArena, but play Nexuiz far too much, so obviously I voted nex.
I haven't tried any yet.
I wanted to have a look at Nexuiz a while ago, but as far as I remember there was some problem. Don't remember if it was the game or my system though.
I also want to have a look into OpenArena, since I always enjoyed playing Q3 (the Linux-version of course).
Since you mention Cube, how about it's successor Sauerbraten? ;-)
Although it's, like Cube, not totally free, I'd just like to mention it since Cube is in the list.
Maybe mentioning cube wasn't the best idea then, but then again everyone can vote so.. As for tremulous I've read about its data license recently and it seems to be all under Creative Commons Attribution ShareAlike which is actually a free license. I know that there was word of it being under non-commercial CC before, but it's possible they changed it now.
My favorites would definitely come down to Nexuiz and OpenArena, but due to it being slightly speedier and the best and easiest to use recreation of Q3A (with even some improvements, and total dedication to all Free Software) I think OpenArena wins for now, for me.