I would guess one of the first was the second BOAC 747 route, which was from JFK to Bermuda. The same aircraft would manage LHR-JFK-BDA and return within 24 hours, so it was operated from day 1. Nobody goes to Bermuda except on holiday, do they ?
For a dedicated aircraft I expect a Laker DC-10 was the first. I think he beat Court Line's Tristars. Liveried up for Skytrain, their first were ABC charters to Toronto and some Palma/Tenerife holiday flights.