Since you're using a Quake 3 map, the classic Quake method of solving this was to precompute a potentially visible set (or PVS) using an offline pre-processor, then do checks against that PVS at runtime to determine what should (or should not) be drawn.
In (very basic) outline, you divide your map into what I'll call "areas"; these could be nodes/leafs in a BSP tree (which was what Quake used), rooms, cubes in a grid, whatever. Then for each such area, you use some brute-force method to determine what other areas are potentially visible from it (I believe that the "potentially" part is on account of some coarseness in the algorithm, as well as the fact that this stage ignores frustum culling which is still done at runtime). Store out the result in some fast and compact data format (Quake used a bitfield array). Then at runtime you're just looking up those stored results, draw calls, overdraw, etc all go down, the map runs faster, and everbody is happy.
The downside is that the pre-processing can take time, needs to be re-run even if you make trivial changes to your map, and needs a custom map format to store the data. And while we're on the subject of formats, .obj is a horrible, horrible, horrible, horrible, horrible format to use for game maps. The only reason to use it is if you really love writing text parsers. The ideal format is where you memory-map a file, read some headers to set up some sizes, then glBufferData the rest. Simple, quick to load, no faffing about. And while we're on the subject of glBufferData, if your observation is that VBOs are slower than glBegin/glEnd, then you're using them wrong: probably by writing a glBegin/glEnd-alike wrapper around the VBO API.