Nice, my conlang got a mention
I haven't made a new phonology in a while... almost tempted to do it again.
The other thing you forgot to mention is an R/L contrast, which is the norm in SAE and much rarer outside of Europe. If you want a language with a less Europeany feel, a quick cheaty way would be to take one of these sounds out. I've currently only got one conlang, Panceor, that distinguishes them (it's the most SAE-like, to the point where I was lambasted for it when I posted its phonology back in 2004 when I made it – see, we've never changed...). Dialectal Sentalian (ie Rempocian, Facurian and Dotolian) does have the distinction, actually, gaining an /r/ from standard Sentalian's /z/ or /ʋ/.
Anyway, personally I never include things like stiff voice or slack voice because I don't actually know how to pronounce them. So I can't be bothered with them.
Initial /ŋ/ is another one that I don't think any SAE language allows, by the way. It's allowed in both Panceor and Sentalian (probably a bit more frequently in Panceor... in Sentalian /ŋ/ and the ejectives are relatively uncommon consonants).Erm, what else? I used the dialects of Sentalian to transform it from something that is relatively un-SAE (although still nothing too crazy – as I say, the ejectives are relatively rare) to something very SAE-like, but in different ways. My aim for the intonation of Sentalian (and currently most of the dialects) is to have rising intonation on statements and falling intonation on questions, the opposite of European languages. That's perhaps a bit simplistic, though.
Umpát and Yaufulti, which are my other two active conlangs, are the ones with more minimal phonologies. Umpát's was provided by roninbodhiwhatsit, but I gave it a few SAE consonant clusters (like /skr/) along with plosive-plosive and plosive-nasal clusters, and then a stress/reduction system which makes it end up not being like SAE.
Yaufulti's original phonology was a hodge-podge of different consonants without much rhyme or reason:
p t f s ʒ x ɣ l ɫ j
but I deliberately tried to subvert a couple of the expectations of SAE and conlangers in general, like a three POA plosive contrast (a favourite myth that conlangers like to trot out), and a total lack of nasals in the language. A couple of odd contrasts were thrown in too, such as two phonemically voiced fricatives, one of which is in a pair with a voiceless one (the distinction is often neutralised, because of intervocalic voicing), and a velarisation contrast on the Ls. The syllable structure is usually CV, but could have a coda L of either sort. But it has to have an onset consonant.
Then there were only four vowels: i u æ ɑ. The idea with the vowels was then to create a very strict stress pattern, with primary stress on the beginning of the word and secondary stress every third syllable after that, creating a sort of dactylic rhythm. Confusingly, the high and low vowels then do different things, because any vowel can be followed by /i/ or /u/ in the same syllable. This means that /ii/ is a long [iː] and /uu/ is a long [uː]. So /i u/ distinguish length but /æ ɑ/ don't – then the idea is that the latter two lengthen in a stressed syllable, while the former two don't. But long /i u/ attract stress and break the dactylic pattern. Anyway, then the 3rd syllable of the word, ie the one before a following stress (and actually even if it isn't followed by a stress this still happens) gets reduced vowels: [e o ə] for /i u ɑ/, but /æ/ just drops out.
Then there's the three consonant processes: consonant harmony (of POA, which only affects the following consonant; and affected consonants can't affect the next consonant), voicing between vowels (except next to /æ/ or a reduced vowel), and palatalization before /i/. Basically just to mix it all up a bit. This creates a few more odd contrasts; at some stage during the language we get a contrast between [β] and [v], and [b] and [bv], for instance.
Anyway, the Western variant of Yaufulti was made as a more reasonable variant; it has /k/ instead of /x/ and /n l/ instead of /l ɫ/, and /ɛ/ instead of /æ/. And the voicing is more regularly intervocalic. Basically I did it because Eastern Yaufulti can be tiring to type with the extra characters. But it makes the thing look like Japanese (but with <l> rather than <r>), which is strange. I also did it because I wanted to incorporate /n/ into the consonant harmony. Mwa ha ha. Anyway, I hope that's sufficiently non-SAE.
Edit: made it small because it's less relevant and more self-absorbed stream of consciousness.