How about some Amazonian languages with unusual phonologies! (My info comes from Dixon & Aikhenvald's The Amazonian Languages rather than from Wikipedia, though in some cases the inventories Wikipedia gives may well be more accurate and based on better/more complete data...)
Maxakalí's consonants are: /p t tʃ k ʔ/, /b d dʒ ɡ/, /h/.
has already been mentioned.
Xavánte lacks velars: /p t tʃ ʔ/, /b d dʒ/, /w ɾ h/.
Some dialects of Madí (Jamamadi and Banawá) have a pretty unbalanced consonant inventory, especially among the stops: /t k/, /b d ɟ/, /ɸ s h/, /r w/.
Jebero has only two ejectives: /kʼ/ and /ɾʼ/ -- the full consonant inventory is: /p t c k ʔ/, /kʼ/, /s ʃ/, /m n ɲ ŋ/, /ɾ ɹ l ʎ/, /ɾʼ/, /w j/.
Another language with an unbalanced consonant inventory, especially in the area of stops, is Trumai: the stops are /p t̪ t k ʔ/, /t̪ʼ tʼ kʼ/, /d/.
Beyond phoneme inventories, there's interesting phonological processes too. In a number of Amazonian languages, "nasal" is a property of syllables rather than individual segments, and there are various types of nasal harmony and nasal spreading, e.g. Tuyuca: bia-ja (close-IMPER, "close (it)") = [biaja], but põõ-ja (open-IMPER, "open (it)") = [põõɲã].
Kaingáng is especially cool in this respect. Basically, "nasal" stops have different realizations depending on whether they border a nasal vowel, oral vowel, or word boundary. If an oral vowel precedes the stop, the stop's onset is pronounced as an oral stop, which then transitions to a nasal stop; if an oral vowel follows, the nasal stop has an oral stop release. A preceding or following nasal vowel means the stop's onset or release, respectively, is fully nasal. Word boundaries work like nasal vowels in this respect. Some examples:
kanɛ̃ = [kadnɛ̃] "eye"
ɛ̃mɛ = [ʔɛ̃mbɛ] "blue sky"
pãnĩ = [pãnĩ] "back"
nɛn = [ndɛdn] "thing"
no = [ndo] "arrow"
nĩm = [nĩm] "to give a long object"
ti no = [tidndo] "his arrow"
no nĩm = [ndodnĩm] "to give arrows"
kanɛɾ = [kadndɛɾɛ] "smooth"