Check the fuse to make sure it's good (prolly is, given the relay click).
It's easy to drop the fan. Three phillips screws, and a simple electrical plug. You might find some crap stuck in the squirrel cage. You can also pull off the top of the fan motor, to see how the brushes look. They can be replaced.
Most likely is the fan speed resistors that have gone. They are mounted in the ducting under the dash, just follow the wires from the switch. Undo the 2 screws holding it in place and inspect the coils, could be where your problem is lying.
mine went. the brushes were shot. when i took it apart, the spring shot acrros the shop floor.....never to be seen again.
i got a used fan from cruiser parts. i think around 60 bucks..but that was a few years ago
Could be that a piece of "foreign material" was stuck in the squirrel cage. (eg a piece of a leaf, hair, etc.)
Could also be that your brushes are wearing down to the end, and as they do so they start to get cocked sideways in the brush guide. They could have gotten sideways enough to jam against the commutator, locking the motor in place.
Or, it could be that the motor just needed somebody to tell it who's the boss!