What is the difference, if any, between these two words?
Yes, while they can mean the same thing, vacation is, also, a time when one decides to have a holiday, while holiday is the time when one does not decide, but when it is decided on some higher level (national, religious, organizational, etc).
Etymology might be enough to see all the peculiarities:
late 14c., "freedom or release" (from some activity or occupation), from O.Fr. vacation, from L. vacationem (nom. vacatio) "leisure, a being free from duty," from vacare "be empty, free, or at leisure" (see vain). Meaning "formal suspension of activity" (in ref. to schools, courts, etc.) is recorded from mid-15c. As the U.S. equivalent of what in Britain is called a holiday, it is attested from 1878.
1500s, earlier haliday (c.1200), from O.E. haligdæg "holy day; Sabbath," from halig "holy" (see holy) + dæg "day" (see day); in 14c. meaning both "religious festival" and "day of recreation," but pronunciation and sense diverged 16c. As a verb meaning "to pass the holidays" by 1869.
EDIT: According to etymology and dictionaries: Chiefly British holidays is a period of cessation from work or one of recreation; vacation.
In the UK "going on holiday" means taking time off, what Americans call "going on vacation". An actual national/religious holiday is not required.
When Americans say "holiday" we mean a specific designated holiday, which we might or might not actually commemorate. For example, most of us don't do anything special for Labor Day, but it's a holiday and a day off from work/school nonetheless. Americans don't say "going on holiday" for that, though; we might "go away for the holiday" or "take time off for the holiday". We might even "go on vacation during the holidays", but "on holiday" isn't how we express it.
The difference between those words is in their use. Vacation is used in American English. It is not used in the English of the English and other British people. The word holiday is the normal word for British people.
Which word you use will depend on if you are speaking American English, or not.
They both mean the same thing.
Some commentator was correct. To an American, holiday means a dictated time or day; days off that the government has seen fit to give (IE: XMAS, New Year, on and on). It's a government-dictated holiday away from work.
Vacation. Your wish to get away from it all perhaps; sometimes including the use of mandated holidays.