Personally I prefer spheres, in fact I made a skybox to skysphere converter for the very purpose.
The problem I have with skyboxes is that once they're loaded, then that's it - you can't change the texture unless everything is limbs. I like to use skyspheres instead, with a moderately low detail level, then it's easy to layer things and change textures, nice for sky transitions with alpha fading. Remember you can set the detail of the sphere when creating it.
With the skyboxes I have used though, I'd concur that they should'nt affect frame rate that badly, matrices can be really slow at big resolutions. Perhaps try that advanced terrain demo, that has a terrain and a skybox, both quite high quality, that should give a decent marker for how it should perform.

Aegrescit medendo