One of the most talked about examples is Piraha[0], a language which doesn't really represent numbers. This is interesting because a study done by Everett and Frank[1] shows that this can actually have effects on cognition, providing some evidence for the Sapir-Wharf hypothesis[3]
[0] https://en.wikipedia.org/wiki/Pirah%C3%A3_language
[1] http://www.sciencedirect.com/science/article/pii/S0010027708...
But I'd bet on the OPs hypothesis as well. At a guess, most space travelling species will have had to climb a similar developmental curve to our own - including agriculture (or whatever passes for it in their biosphere, unless they photosynthesize themselves), tool making, metal smelting, nuclear power, etc. etc.
Given that there is so much of physics that we have yet to understand (assuming what we think to be true is actually true), and given the infinite possibilities of what forms alien life could take, you can't make any assumptions about what sort of language they'd have. This was a point they briefly tried to make in the movie.
If I had to boil it down to a sentence, Everett's claim ultimately was not that the Pirahã can't think recursively, it's that their language reflects a cultural aversion to referring to things that aren't concretely present, and this impacted their grammar for subordinating clauses.
OTOH, and quite separate from the recursion issue, there has been some really interesting research on Pirahã perception of number. The ScienceDirect link/paper in the parent is well worth your time; it's also here https://www.researchgate.net/publication/5308732_Number_as_a... and background at LanguageLog http://languagelog.ldc.upenn.edu/nll/?p=341
The short of it is that Chomskyan hypothesis has a giant edifice built upon a single central idea. A fraca in popular science (i.e., outside academic journals) arises between Chomsky and Pinker over these ideas. Some unknown researcher announces that his obscure language brings the whole edifice crashing down. Add in a touch of Sapir-Whorf to make accusations of racism credible, and Chomsky's well-known fondness for dismissing critics rather than engaging them in scholarly debate.
Basically, there were two debates (did Pirahã have recursion in the sense that Everett meant? and what constitutes proof or disproof of universal grammar?) that went on simultaneously, while someone apparently took the opportunity to smear Everett with the Pirahã study ban.
I don't believe in the existence of a set containing all natural numbers at the same time, except as an idea to talk about.