I’ll give you a language you can make a long day trip to hear - Basque.
Basque has a bad reputation among linguists for difficulty when one is trying to learn it the old-school way, in a classroom setting. The grammar is pretty daunting because of many linguistic factors.
To bowdlerize considerably, Basque words just seem to change too damn much, even to convey the slightest shades of meaning. In English, you could ask for ‘some ketchup’, ‘a spot of ketchup’, and ‘lots of ketchup’ – and the words ‘some’, ‘spot’, and ‘lots’ can be used similarly with many different things (mayonnaise, praise, rain, etc.) In Basque, however, you can’t do that – it’s more like ‘ketchupaz’ means ‘some ketchup’, ‘ketchupiza’ means ‘a spot of ketchup’, and ‘ketchuporza’ means ‘lots of ketchup’ (not real Basque endings). Plus, those endings may or may not be applicable to different words, so the memory of the Basque learner is pushed to the limits. Mentally sorting and choosing the right form in which to use a noun really can mess with one’s attempts at Basque fluency.
That’s only one difficulty with Basque. Another is the wide use of the ergative construction, which (very roughly) reverses the concepts of Subject and Object in Basque sentences … but not always! When the ergative construction is used and when it is not can seem pretty haphazard and counter-intuitive to a non-native Basque speaker.
You may think you’re ordering a latte in a Bilbao cafe, but your Basque waiter hears ‘A latte is ordering me’! Then you go down the street to the butcher shop. To compensate for your coffeeshop foible, you tell the butcher in Basque that ‘Some beef orders me’. But no! You should NOT use the ergative in that case! You should have just said ‘I’d like to order some beef’! (not real Basque examples, but you get the idea)!
All that said, I doubt learning stock phrases (‘One beer, please’, ‘Where’s the bathroom?’, etc.) are any more difficult in Basque than in any other language. Also, Basque words are very easy to learn to pronounce - no tricky sounds.
Other European contenders include Hungarian (complex grammar) and Estonian (tough pronounciation).