Which language would you choose ?
Perl, Shell, C/C++ with binaries pre-compiled ?
Shell has the problem of being inconsistent across several platforms.../bin/sh on Linux systems (except Ubuntu) is BASH, but on FreeBSD, Solaris, and others it is a classic shell. If you are extremely careful, you can write in very standard sh, but it's a pretty challenging language to build anything bigger than 100 lines or so (I built our installer in sh, and I've regretted it ever since it grew up to about 300 lines...it's now at 1143 lines, and I'm in the midst of translating it to Perl, where it will be dramatically shorter and more powerful.
Anyway, Perl is pervasive, and has been backward compatible for about a hundred million years. I have code that I wrote 11 years ago that runs unmodified on modern Perl 5.10. This means that if you target, say, Perl 5.8, you can expect your program to run on any system that has pretty much any Perl version less than 7 years old. (If you go back too far, you lose a lot of really nice features that make programming in Perl enjoyable. Unicode didn't get perfected in Perl until 5.8.2, I think, maybe 5.8.4, so we consider that our baseline and what we target.)
Python, while it's very nice and also widely available on many platforms, is not particularly backward compatible. If you target Python 2.4 or 2.6, it will not run on Python 2.2. If you shoot for a least common denominator, you will still find there are some incompatibilities. I worked on several Python projects a few years ago during the transition from 1.5 to 2.0, and that code required serious changes...then several minor changes from 2.0->2.2->2.4. I wasn't around on those projects when 2.6 came along, nor 3.0, but I get the feeling that both required some changes and brought some incompatibilities. While this may lead to a cleaner language, it means you have numerous concerns about cross-platform compatibility, and your testing requirements go way up. My Perl testing environment consists of a Perl 5.8.mumble installation, and nothing more. If it runs there, I know it'll run on every version from then up to 5.10.x, which spans about seven years worth of Perl versions.
Binaries are practically impossible for this task. People expect native packages, which are extremely time-consuming to build and test. Linux distros break backward compatibility in their libraries regularly, so you'll have to ship statically linked binaries. On platforms that don't break backward compatibility, like Solaris, you still have to assume a pretty minimal environment, since those systems are quite anemic on the library front, so again, you're shipping statically linked binaries. And, the moment you get a customer that wants it for some whacked out platform like HP/UX on Itanium, you'll be kicking yourself...and you will get customers running bizarre systems, if you call yourself cross-platform.
If you need an X-based GUI, Tcl/Tk might still be the best choice (five or ten years ago it was the only sane choice for such a creature). Perl has good bindings for Tk and WxWindows, but neither is likely to be available. Python has Tk bindings out of the box, so if you hate Tcl, and like Python, and need a GUI, this might push Python into the lead. The biggest problem with Tcl is that it's just not very active or growing. Perl and Python, on the other hand, have very vibrant communities. All are pretty good languages, though, in their own way...though I never really got the hang of Tcl whereas Perl and Python seemed pretty natural.
To pile on the anecdotal evidence, my co-founders project, Webmin, is probably one of the most cross-platform pieces of software in existence...supporting at least 150 different operating systems and versions (the last time I counted in 2003, it added up to about 150 variants, not including architectures, and probably 30 or 40 new variants have been added since then). It's about 350,000 lines of Perl, plus a touch of sh for the installer.
Of course, this assumes all things being equal. Do you hate Perl? If so, it's probably not worth working in it just for compatibility (though I suspect you don't know modern Perl very well, if you truly hate it). You can just tell your customers to install Python, if they don't have it, or upgrade if they do. I find the two languages roughly equal in terms of how much I like working with them, and how productive I can be.
The other cool choices, like Ruby, Lua, Lisp, Haskell, all have the problem of being unavailable, by default, on most UNIX systems...and so you'd have to support your users in installing the language, as well as your app.
Bash is supposed to behave like sh if it is invoked as /bin/sh. (I'm not sure how good a job it does at this, but at least it tries to be standards-compliant.)
Mostly, I found everything I needed in this Ubuntu guide:
https://wiki.ubuntu.com/DashAsBinSh
So, the BASH/sh dichotomy is not traumatic, by any means. At least not on the platforms I've dealt with it (which, so far, is only Linux of many flavors, FreeBSD, and Solaris--so there may be more issues in the future). But, since there are so many other negatives to working in sh for anything more complicated than a one-off script, I'd probably go for a language better equipped for modularity. Since Perl is pretty close to standard on every UNIX I've ever used, I don't think you lose much, if anything, in the way of cross-platform.
It's been a few years since I dealt with distributing C across many platforms, but I can't imagine it's changed dramatically for the better (since make has been famously painful for about as long as it has existed).
I believe it's the same for some linux/BSD flavors and installation options.