You should start with consonants, I don't think you can make a vowel inventory as weird as a consonant inventory (maybe complex tones? creaky voice?). After that, it depends on your opinion of "particularly difficult" and "unnatural and weird".
- Click consonants can be easy enough if you don't overdo it (more like Bantu languages/Damin and less like Khoisan languages, so only the simple ones).
- Retroflex consonants are also not very European and sufficiently easy to pronounce, but maybe not noticeably weird.
- Ejectives and implosives are similar, but much more noticeable.
- Linguolabials sound and look weird (especially the trill) and are very easy to produce. Same goes for bilabial trill.
- Prenasalization, unclosed plosives and similar modifications are non-European (I don't know much about their ease of pronunciation).
- You could go with something like Kaybop and have manual percussives (Kaybop has clap [bimanual percussive] and facepalm [faciomanual percussive]), which is very unnatural (maybe a bidigital percussive?). These are weird no matter what you say. Also from Kaybop: Phonemic hats.
Klingon frequently uses velar and uvular voiceless sounds, which gives it its typical Klingonyness. You can also remove areas of the IPA (note that it is unadviced to just remove certain sounds), where you can choose randomly from removing all voiced, voiceless, labials, alveolars, velars, plosives, fricatives and so on, or make phonemes from any area noticeably more frequent.
Then there are phonotactics. Many European languages have consonant clusters, so a syllable structure like CV or CVC has an exotic feeling (just look at Austronesian languages like Hawai'i). Ithkuil on the other side is weird because it has so many consonants (and vowels) and very complex clusters.
This concludes my advices, but there are probably many more things fitting your description.