There are probably more formal answers, but for me it boils down to what kind of shot I am looking for.
If I want to register something in time (either frozen or moving) then shutter speed is more important than aperture.
If I want to register something in space (meaning a deeper or shallower area in focus) then aperture is more important than shutter speed.
Note that this doesn't mean necessarily using shutter priority or aperture priority in either case. The point is determining what is more important in my vision of the shot, time or space, and then choosing the best camera mode for that.
I have to agree that S/Tv and A/Av modes are easier to use when prioritizing speed or aperture, but once you get used to the relations between speed, aperture and ISO and the way your camera handles the exposure calculations, it is not that hard to use almost any mode (including P - Program Exposure) to take your shot.
As lindes pointed in the comments, let's not forget Manual mode (M) with its full control of the variables involved. Just keep in mind that when using Manual, the camera will not compensate any light changes that happens after you set the values, while the automatic and semi-automatic modes allow the camera to keep your desired exposure levels by changing the free variables (the ones not set by you).