Of course, cube maps can only be created with a 90° fov (at least if the camera is positioned in the cube's center). Otherwise, you would not get a cube. If you decrease the fov, you will get empty spaces around the edges. If you increase it, you will get overlapping areas. You could also create a cuboid from non-90° fovs, but that wouldn't be worth the effort.
The addressing mode of cube maps in OpenGL is different than the one used for ordinary 2D textures. You access 2D textures with a 2D texture coordinate. Cube maps are accessed via a 3D direction vector. OpenGL then uses this direction vector to calculate the sub texture to use and the texture coordinate for this sub texture.
A skybox can also be easily implemented with six plain textures. In fact, the advanced addressing mode may even turn out to be a disadvantage in this case. It would be different if you used a different sky carrier object (e.g. I once used a sky tetrahedron). If there were distortions, there must have been some mistakes in your code. The basic principle works.