Oh, and I realize that almost all of the examples of holidays on here are religious, but that's not part of the definition. For an American, Thanksgiving and Independence Day are holidays. Halloween, and Valentine's Day are also holidays even though they're normal work days.
"on holiday" is British, or UK English; "on vacation" is American- there is no difference other than that. "Holiday" is used in the US to denote special days on the calendar, such as Christmas, Chanukah, Ramadan, Kwanzaa, etc. "Holy Day" is used to denote such special days when they have religious significance, but generally only by the Church. It is the linguistic root of "holiday," though, as I suspect you know.
The phrase is "on vacation," without the article. "On a vacation" might be used to distinguish why the person is absent, "He's sick" or "He's on a vacation." It is most often used when followed by a noun, such as "on a vacation day (week)." "On the vacation" might be used in recounting what happened during your trip, though most Americans would likely use "on the trip" instead. If they had what is currently being called a "staycation," meaning that they took vacation time but did not travel, they might use "on the vacation," to say something like, "You will never guess what happened on the vacation." Even then, most Americans would rather say something like "on our vacation." Hope this is helpful!