I have studied Japanese and Spanish at the university level, and, at least at my school, the Japanese program is much more in line with what I assume your preferences are.
As a linguistics major, I prefer more rigid/traditional instruction in a language where the syntax is learned first, followed by the phonology, and then vocabulary/idiom. I loathe learning "common phrases" and "situations" before learning the underlying structure, because I believe that it is: counter-productive since one is inclined to translate phrases as a unit, and inefficient since one has to "re-learn" why the phrases are constructed in the way that they are.
If you would like to learn a language in the manner that I described, I would suggest taking a language that is offered by the Linguistics department of your school instead of one offered by the Foreign Languages department (assuming such distinctions exist). When a language is taught by a linguist, you can bet that syntax and morphology will get its proper due. The only caveat is that the Linguistics department usually only provides instruction in obscure or "dead" languages, and that might not be what you're after. For example, Irish Gaelic falls into the Linguistics department at my school.
If you're looking to take a widely spoken modern language, then it is more likely that a non-Indo-European language would be taught more rigidly. The reason is that it is much more difficult to translate utterances directly from say English to Japanese than English to Italian (substituting German --> X would be very similar). Since my only experience with non-European languages is Japanese, I'll do my best to explain why the language has to be taught in such a way.
Example:
Japanese: Tokyo-kara Osaka-made jitensha de go juppun gurai desu.
gloss: Tokyo-from Osaka-to train-(by means of) fifty minutes approximately is.
translation: It takes approximately fifty minutes to go from Tokyo to Osaka by train.
Note: I have no idea how long this trip actually takes 
As you can see by looking at the gloss, learning Japanese vocabulary without an in-depth knowledge of the syntax is almost worthless; whereas, if a speaker of English learned Span. "mi" = Eng. "my"; Span. "coche" = Eng. "car"; Span. "es" = Eng. "is"; and Span. "nuevo" = Eng. "new". "Mi coche es nuevo." would be intelligible. Compare that to "Watashi no kuruma wa atarashii desu." gloss: "I-possesive car-(as for) new is".
Good luck finding a class that is taught in a way that you prefer.
