The minimum you can expect to find on any unix system that's not antique or embedded is POSIX/Singe UNIX. Specifically, all current unices mostly conform to POSIX:2004, a.k.a. Single Unix issue 6. This gives you sh, sed and awk as programming languages.
If development packages are installed (which they often aren't on a server), you can do development with cc (C compiler), lex, yacc, make; but apart from make these aren't useful on the machines you'll deploy your application to, only on development machines.
If you assume Linux, most distributions follow the Linux Standard Base to some extent. The LSB goes beyond POSIX. The core specification includes a C runtime with support for multithreading, NSS, PAM, ncurses, libz, SSL and a few more libraries. The LSB doesn't require bash, only a POSIX sh which could be ash or ksh, but in practice most non-embedded Linux distributions ship bash as part of the default installation. The languages specification includes Perl and Python. In practice, not all distributions make full LSB support part of their default installation, but you can generally make a good case that if it's specified by LSB (but not in the LSB desktop specification, obviously), it should be installed on a Linux server.
On other systems, Perl is very often available. Python is not as common but gaining popularity. You can pretty much count on either bash or pdksh (but not always; IIRC NetBSD only has ash in its default installation). For compiled languages, you'll always find a C runtime and almost always find a C++ runtime.
awkin your list – rmflow Jun 23 '11 at 10:56grep,make,sedand evenyacc. – Vlad Jun 23 '11 at 11:01