That was the trick - thanks!
Hold the volume up and focus until the recovery shows up, you only have to hold the power button until the phone vibrates once.
Also in case it helps anyone else, "Partition SD" is found under Advanced Settings in the Recovery menu.
I chose 1GB as I have a 32GB card and hopefully have some margin for error, but I couldn't find any clear guidance on how big it actually needs to be (or whether it's possible to resize it afterwards).
Edited by mr-brunes, 07 January 2012 - 03:34 PM.