As suggested in the question, symmetry tells us that the caudal (tail) fin of a balanced, neutrally buoyant, underwater animal or vehicle in an isotropic unbounded aquatic environment should work equally well at any angle. This is why studies of hydrodynamical caudal fin efficiency or the fluid mechanics of oscillatory swimming can ignore the orientation of the fin.
This isotropy argument fails, however, if the symmetry is broken because of, for example:
- a preferred (typically horizontal) plane of movement,
- deviations from neutral buoyancy,
- proximity to a water-air or water-bottom interface.
In such cases it may be advantageous to have better manoeuvrability in a particular plane. Caudal fins are more effective in driving acceleration in directions at right angles to the orientation of the tail, so a caudal fin orientation perpendicular to the preferred plane of movement would usually be more effective.
Vertical tails improve horizontal manoeuvrability
As noted in @Andrew-Steane's answer, fish often prefer to move in horizontal layers of water with specific salinity, temperature, and light levels, or distance from the surface or bottom.
A horizontally flexible body with a strong vertical tail exerts its forces in the horizontal plane and hence can drive horizontal changes in direction (yaw), maximizing manoeuvrability in the preferred horizontal plane.
If, has been argued, fish first evolved in shallow intertidal-subtidal environments, it is possible that horizontal mobility and hence vertical tails gave an evolutionary advantage.
Horizontal tails provide more direct control of horizontal trim
Deviations from neutral buoyancy require corrections from horizontal (or at least non-vertical) control surfaces to correct ("trim") undesired deviations from horizontal motion.
Aquatic animals are generally close enough to neutral buoyancy to be easily trimmed by relatively small ancillary control surfaces (e.g. pectoral fins) and body shape, but one advantage of horizontal caudal fins is that they can provide both propulsion and horizontal trim control.
Most independently evolved aquatic thunniform animals such as sharks, tuna, and ichthyosaurs, all have (or in the last case had) vertical caudal fins and pelvic fins to help control trim. Extra fins increase drag, however. With horizontal caudal fins, evolving dolphins did not need their hind pelvic limbs/flukes for trim control and have completely lost them, reducing drag.
Horizontal tails improve vertical manoeuvrability
In contrast to fish, aquatic mammals need to breathe air so they are frequently moving vertically up to and down from the water surface, so their horizontal tail is well matched since it is optimal for driving changes in vertical (pitch). This can be particularly helpful when they are moving long distances at speed and need to breathe frequently. Simply swimming on the surface is less efficient because of surface-wave drag, so fast moving aquatic mammals typically swim below the surface coming up briefly for air, or engage in energy-saving porpoising where they spend a significant fraction of their time out of the water completely. Such movements are easier with their horizontal tail.
Biological evidence that horizontal fins are not better
Finally, it is fun to note that there is a strong biological evolution argument that horizontal fins are not better than vertical fins for propulsion. Flatfish with horizontal tails are closely related to the billfish (sailfish, blue marlin, sailfish,…) that are the fastest fish on Earth. Also, some fast sharks frequently swim rolled on their side by up to $60$° in order to take advantage of vertical lift provided by their large vertical dorsal fins. There is clearly no significant evolutionary barrier preventing fish from evolving to swim on their side, so if having tails in a horizontal orientation moving vertically was significantly more efficient, this would be used by at least some fast fish.
For additional information from a biology perspective on this interesting biophysics question, see "Best tail for swimming?" and "Why is there a difference in the rotation of the tail fin in fish compared to marine mammals?".