I actually took a more detailed look at a few of them, since the first time was more of a quick glance. After viewing the Nomad hall a little more, I think it probably would be the best choice. It's open and expansive, fairly interesting, has those cool teleporter things, and plenty of good places to fight. It does have quicksand, but that actually could be a positive aspect strategically. Only one central area is quicksand, and you can avoid it in most cases if you want to. However in Capture the Flag it's necessary to travel across it to get the flag, and this adds in some tactical elements. Also it could be possible to halt an enemies advance by getting the quicksand between you and them, so they either have to go around or be mowed down as they run across.
Frozen could also be quite good, I like the look of that one too. I have to say I'm not such a fan of the Isle of the Dead, it's nearly all so narrow and confined. It does look kinda cool, but I prefer the scenery of some of the more open halls.