It honestly depends on a host of factors.
1. Do you plan to stay in the Navy?
If so, you should know that there are certain languages for which you can receive a "Foreign Language Proficiency Bonus". Certain languages pay a lot, others don't:
404
2. Do you want to learn a language that a lot of people know, or be the one gal/guy in the room who speaks a uniquely helpful language?
As an example, a friend of mine doing clinical rotations in Saint Louis initially regretted not taking Spanish in college since so many of his patients spoke the language. Thankfully, enough of his peers spoke the language that he could always call for assistance. In contrast, almost no one spoke Russian -- so the few times they actually had to treat a patient from one of the former Soviet Republics, my friend was in a unique position to help (since he'd taken two years of it).
This is why I don't always agree with the default recommendation for all medical personnel to learn Spanish (though I wouldn't necessarily discourage it, either).
3. Do you want to learn a language that's useful in a lot of regions, or something that's useful to a particular community/people group you have a lot of interest in?
Take Bengali, the language spoken in Bangladesh and a number of states in India. By number of speakers alone, it's the sixth most popular language in the world. Yet its use is basically confined to a very specific geographic region. (The same thing for Korean -- not a lot of people outside of Korea speak it, but if you like Korean food, live around a lot of Korean-Americans, have a crush on some Korean girl, etc....)
Contrast this to French, which is used (in some version) throughout Europe, western and central Africa and several countries in the Caribbean -- or to the geographic spread of Arabic, which devout Muslims from Morocco to Indonesia can at least read.
4. How important to you is the language's association with cultural, economic, and/or military power?
Yes, lots of people speak Arabic, French, and Spanish. However, I would argue that the people groups who speak these languages are losing their cultural, economic, and military influence when compared to countries on the rise in Asia, specifically the People's Republic of China. You could counter that the use of Chinese is largely geographically concentrated in, well, China (it's not like they speak it in neighboring countries like Korea, Japan, Mongolia and Vietnam). However, it cannot be denied that China will continue to influence global trade and international relations for the near term (and that literate Koreans and Japanese also understand Chinese characters), so if this is important to you....
5. Do the speakers of your foreign language also speak English to a high degree of proficiency?
Germany is Europe's biggest economic power and its language is spoken throughout the continent. However, speakers of German generally tend to be proficient in English as well. The same is true for most Europeans -- from personal experience in Afghanistan, the various European members of ISAF (the French, Italians, Estonians, Danes, etc) get along just fine in English. This is also the case in many parts of Japan and Korea. Of course, if you go to the countryside, you'll find few English speakers. But again, if you're mostly dealing with fellow physicians or military officers, an overwhelming majority of them will speak English to some degree -- or at least enough for you to get by.
Contrast this to the variants of the Persian language. Whether you call it "Dari" (Afghanistan), "Tajiki" (Tajikstan and Uzbekistan) or "Farsi" (Iran, Qatar and the UAE), most of the speakers I've met -- with the exception of the very educated -- cannot speak English to any degree of proficiency.
6. Do the speakers of your foreign language also speak a "mother tongue"? How many people actually speak it as a native language, as opposed to a second language?
Take Swahili. Yes, it's an official lanuage in Kenya, Tanzania, and Uganda, but most of the Kenyans I know are more comfortable in their "mother tongue" -- like Kisii -- or in English, since it's the language of international business. Swahili is just something that they learn in school and then never really speak at home or at work -- sure, 40 million people "speak" it, but less than a million consider themselves native speakers. I would argue that Hindi is somewhat similar. A lot of people speak some version of it (and Urdu, its cousin), but people in India also speak another "mother tongue". (Moreover, most Kenyans and Indians speak English -- see #5 above.)
7. How easy will it be for you to learn? Will you be able to immerse yourself in the language either through study or work abroad? If not, are there native speakers of the language in the area in which you live and work?
Finally, I would make a pragmatic argument for how easy it'll be for you to pick up the language and sustain proficiency. Arabic, Chinese, and Korean are notoriously hard to learn (they have the longest courses of study at the Defense Language Institute). Moreover, I would argue that you can't truly learn a language unless you're living it out everyday, and I would also argue that language is a perishable skill that will diminish over time in the absence of practice. So let's say you try to learn Chinese, but never really have an opportunity to live in China -- how proficient can you truly become? And let's say you do move to Beijing for a few years, and get so good at the language that you pass for a local. But then you return to the States and live in Omaha or Phoenix as opposed to San Francisco or New York. How are you going to practice with a native speaker? How much are you going to retain over time?
To answer your specific questions:
"For the Navy guys who have been abroad, how much would Japanese, German, or Korean have helped in those locations (i.e., how many people spoke English)?"
Of course it helps, but see #5 above.
"Anyone betting on a war in Asia, or maybe Africa (french) that are worth preparing for?"
Well, I would cite the Sicilian proverb that you should never start a landwar in Asia.... In all seriousness, I don't think there'll be a war in the World War II sense (or even the OEF/OIF sense), but I would bet my next paycheck that the US will be involved in some way shape or form in the Pacific for a long time. Thus, Chinese would go a long way (see #4 above). As for French, also a good bet -- the US military will increasingly shift to foreign internal defense/security force assistance and/or humanitarian relief and development. A lot of that will take place in the Horn of Africa (yeah, they speak French in Djibouti), but I also think we're going to start getting involved in the Sahel (yeah, they speak French in Senegal, Chad, Mali, etc).
"Were there any other languages you wish you had for CONUS locations?"
Spanish, but you already speak that.
"Again, this is just a hobby. I'm leaning towards either Korean, Thai, or Hindi right now."
I would lean against Korean (see #3 and #5), Thai (see #3 and #7) and Hindi (see #3, #5 and #6).
My recommendation is that given your medical career, Navy service (however long that would be), and most importantly, the fact that you already speak Spanish, I would go with French for your third language. You may get the Navy to give you some extra money (#1), you could very well be the only guy in your clinic who speaks it (#2), it's useful in a lot of different places (#3), and since the grammar is so similar to Spanish, it should hopefully be easy to learn (#7) and retain (depending on where you live/work).