Valencia, depleted by injury, came from behind to win 2-1 at 10-man Girondins Bordeaux and underline their status as competition favourites.
Newcastle United also gained the upper hand on their travels, drawing 1-1 against PSV Eindhoven to take an away goal back to St James' Park for the return leg on Wednesday.
European debutants Villarreal, who had played six Intertoto Cup and eight UEFA Cup games to reach this stage, served further notice of their blossoming pedigree by threatening Celtic's long unbeaten home record stretching back to August 2001.
The Spanish side led through an early Josico goal and spurned other clear-cut chances to add to their tally before Larsson hauled the runaway Scottish premier league leaders level just past the hour.
Villarreal weathered early Celtic pressure before stunning the hosts on nine minutes. Joan Roman Riquelme's corner was cleared as far as Roger and his cross from the left was glanced home by Josico.
Former Barcelona and Olympique Lyon striker Sonny Anderson and Jose Mari wasted great chances before Celtic replied with Stilian Petrov's effort turned on to the post by Jose Reina.
In an explosive start to the second half a clean through Anderson was denied by Celtic goalkeeper David Marshall and then Sebastian Battaglia crashed a 30-metre effort against the bar.
Larsson had a goal ruled out for handball when a clearance from Reina crashed off him into the net but the Swede was soon celebrating when he connected with Didier Agathe's cross to head Celtic level on 64 minutes.
Three-times UEFA Cup winners Inter, Italy's sole remaining representatives in European competition this season after AC Milan's stunning Champions League exit on Wednesday, will have to score in the return at the San Siro after an ultra-defensive show at the Stade Velodrome against Marseille.
Alberto
DROGBA BLOW
The striker's celebrations proved bitter-sweet though. He was booked for over-exuberation and now misses the second leg through suspension.
"Didier's yellow card is a big blow, I hope the players will qualify for him," said Marseille coach Jose Anigo.
Two goals in the final 15 minutes from Ruben Baraja and Francisco Rufete gave Valencia, seeking to become the first Spanish winners of the UEFA Cup since Real Madrid in 1986, a hard-earned win in Bordeaux.
Valencia keeper Santiago Canizares, deputising for the injured Andres Palop, gifted the French side the lead on 19 minutes when he allowed midfielder Albert Riera's free kick to bounce in front of him and beat him at the near post.
English referee Mike Riley then booked two players from each side before showing the red card on 27 minutes to midfielder Rio Mavuba for kicking out at Mohamed Sissoko.
Bordeaux defended stoutly but the Spaniards finally made their extra man count on 75 minutes when Baraja exchanged passes with Sissoko and crashed a shot past Ulrich Rame.
The winner followed three minutes from time, Rufete netting after his own shot had struck the post.
Newcastle's last trophy was the Inter-Cities Fairs Cup, the forerunner of this competition, 35 years ago but Bobby Robson's side can start dreaming of another after frustrating PSV at the Philips Stadion.
Jermaine Jenas headed an equaliser on the stroke of halftime, nodding home a Laurent Robert free kick to cancel out Serbia and Montenegro striker Mateja Kezman's superb 15th-minute opener for the Dutch hosts, whom Robson led to two league titles in the 1990s.
Kezman opened the scoring when he received the ball from Jan Vennegoor of Hesselink, beat off a weak challenge from Aaron Hughes and gave Shay Given no chance with a curling shot into the top corner.
