It is extremely rare to find a computer without the JRE anymore. I am certain that the number of personal computers with Java outnumber the number of personal computers running Windows (or anything else), hands down. However, C/C++ will make a very solid program, provided it doesn't do anything dangerous; and provided that it's just a command-line program, it can run on multiple machines if recompiled for the major ones and all versions are released. Java is not as solid (fast/low-level), but it is safer and much more universal.
However, something that can run in a browser (JavaScript, PHP, etc.) would be even more universal
...But all in all, C++ is a pretty good choice. I just think Java is more accessible.
As for [insert linux distro that nobody is going to have unless they are computer savy enough to make downloading a JRE trivial ...] users, are you that bent against not having Java (the "write once, run anywhere" language) on your machine!? Whenever I found a computer without it, I'd always "fix" it, since it "should" be there ... but that's rare now. ... But I hear ya, because I was bent against having the .NET framework on mine (pssh, you certainly can NOT just expect that to be anywhere ... though C# is amazing).
...Sorry, this is getting a bit out of hand. Java was a suggestion because (aside from the let's choose an obscure OS that is in the 1% of those without Java) it's universal. But that's to say that one language is better than another, and that is certainly not true; it's all preference. If you prefer C++, use that because TONS of software for ANY platform is written in C++. When you look for software online, you find an exe or whatever works for your OS anyway