Start your Mac and install
this utility from Apple. Run the utility to make a recovery USB key with your new USB key. Leave the USB key in and reboot while holding the option key. You should get a boot selector screen showing the orange USB key as a boot option. In that screen select the USB key to boot from.
That will get you to a recovery screen that looks like the one you saw before. The difference is this one is running off the USB key, and not your Mac's internal drive. Now start Disk Utility and select the top choice in the Disk Util list and erase. Once that is done, go ahead and click to install the OS.