When should concurrency and parallel multi-processing concepts be introduced?
If we don't introduce parallel/concurrent thinking early, our students can develop a sequential mindset that makes it hard for them to make the shift later. The rest of this is in the context of a college/university CS curriculum...

Multithreading can be discussed in CS1 if the students build GUIs, since the GUI needs its own thread to maintain responsiveness while the main thread is handling time-consuming GUI events.  But most GUI libraries do this multithreading for you, so the students don't have to do it themselves -- you can talk about what's going on under the surface, but the students don't gain any hands-on experience and it's unclear to me how much they take away if they don't have to do it themselves. But there are schools that take this approach.

We introduce students to multithreading in CS2 (Data Structures), using Just-In-Time pedagogy.  The basic idea is to give the students a problem that requires them to store a lot of data in a data structure (e.g., an organism's genome in a C++ vector or a Java ArrayList, or a really big image to be processed) -- enough data that processing the data sequentially takes 5-15 seconds.  This is an eternity for todays students and they get impatient waiting so long for their program to solve the problem.  We leverage that impatience and use it as motivation for introducing multithreading and parallel execution as a means of speeding up the program. We think the CS2 (Data Structures) course is the first time there is a natural motivation for introducing multithreading, since that's the first time you can store enough data to really motivate it.

Our CS3 course is an Algorithms course, so we continue the exposure there by introducing parallel versions of searching and sorting algorithms, graph algorithms, etc. 

Our fourth course is Programming Languages, where we spend 1-2 weeks on languages that provide features for parallel / concurrent execution.  For example, we contrast languages that expect threads to communicate via shared memory (and the different mechanisms to synchronize those accesses: semaphores, locks, condition variables, monitors) with languages that have threads communicate via message passing (e.g., Erlang, Scala).

Our sixth course is OS &amp; Networking, where spend several weeks exploring the implementation of the features needed to do all of this: threads, processes, semaphores, locks, condition variables, message-passing systems, etc.

The upshot is that parallel and concurrency topics are "sprinkled" throughout our curriculum, rather than being confined to a single course.  (We also offer a junior-senior elective course that focuses solely on parallel computing, so that students who want more can dig deeper into the subject.) That's one way to do it.