What should I have done?
I agree... my first reaction is to sheet out the main to depower it, then bear off a bit... heading up is good if you can''t uncleat the main, but it causes extensive flogging.
One other option, though it probably wouldn''t work with a big genoa up, would be to instantly tack, but leave the headsail cleated on the new windward side (backwinded), then push the tiller to leeward (turn the wheel to windward) and lock/lash it to effectively heave-to. Then, you could probably start to reduce sail... heaving to is a good tactic to learn, so, try it out on a less windy day to see how your boat responds.
Anyways it sounds like you did just fine!