Yes learn Mandarin and Cantonese at the same time. It will be great for your pronunciation practice. You won't get confused with the different intonations at all. Even better, learn Mandarin, Cantonese, Taiwanese, Thai, and Hakka at the same time for extra pronunciation practice.

As Chinese Teacher John pointed out already, it is not the whole southern of China that speaks Cantonese. It is mainly Canton (Guangzhou) that speaks Cantonese. However, even people from Guangzhou speaks Chinese Mandarin as it is the official language of China. So you should have no problem traveling throughout China with Chinese Mandarin. The only possible trouble I can think of is the accents. As of your question, I think it depends on your learning style and how you want to tackle it. For example, taking your route, I would agree with you that it is best after reaching some level of fluency in standard Chinese before moving onto Cantonese. I would say after you have reached intermediate or higher (or conversational depending on your purpose), then you should be fine. Now, if we think of it another way... you may actually be able to tackle both Cantonese and Mandarin at the same time. The similarities in term of writing might be advantageous for your learning purpose (<-- this largely depends on your learning style as it can be either be advantageous or disadvantageous). I can't go too much in depth for this method as Cantonese isn't my strong field haha. Maybe someone else can expand on this idea if you were to take this route. It is probably safer to go with the first route. 加油! (^_^)

You should know that only people in Canton province speak Cantonese. We have over 20 provinces in China, original they all have their own accent instead of Mandarin. So only Mandarin makes people all over China understand you.

Doing two tasks same time means twice more efforts and twice longer process. How about one by one? Chinese is easier than Cantonese and used in more areas thus i'd recommend to start with it.

The people who speak Cantoness are mainly living in Candon (Guangdong), Hong Kong, and Guangxi.