SkyBox? When?

Just put your skybox''s faces very far, ie near your frustum !

Well, I didnt want to do that becouse I also have terrain that, in most cases, stretches out to the far cap plane, and I dont want to cap off even more of it with the sky box, but if thats the only way - Ill just have to live with that.

No don''t do that, the skybox only needs to be big enough to enclose the camera. Its usually in front of alot of other scenery. Its like smoke and mirrors really lol. If you render your quads at the extent of your clip planes they''re going to have to be huge. Rather render the skybox last and disable Z testing so you don''t occlude any pixels already written to the frame buffer thus generating the illusion that its behind everything else.

Err sorry, you need to render it first without Z testing so that depth info isn''t written to the Z buffer then turn Z testing back on and render your terrain which will occlude parts of the skybox. That should do it