The recovery partition is normally not free; it's normally full, and holds the files and tools needed to re-install Windows. Thus, it appears as if that partition may have been damaged or modified already. If so, you might want to take extra care to keep backups of your Windows installation, so as to enable you to restore Windows in case of problems. Alternatively, if you've got a retail Windows 8 DVD, you should be able to use that to restore the installation. In either of these cases, deleting the recovery partition should be OK.
That said, you might want to shrink your
C: partition to make room for Linux, especially if you want a big
/home directory. Although 15GB is enough space to hold Linux, it's not enough for a big Linux installation, especially not if you expect to store big user files on a Linux filesystem.
Note that an EFI-based installation uses GPT partitions, which aren't limited to four primary partitions the way MBR partitions are. Thus, you'll be able to create several new partitions for Linux, if that's your concern, without causing problems.