As for what microcontroller to actually learn on, I would say the MSP430 is a very good starting point. It's a fairly mundane 16-bit RISC microcontroller series with very forgiving electrical design requirements, very good documentation, and very good community support. They make a devboard (TI calls them Launchpads) for the MSP430G2553 that's more than enough to get a beginner started. When you need a little more power, you can either opt to invest in learning the ARM ecosystem, or go for something a little more exotic. Just about every manufacturer makes an ARM microcontroller of some sort, so if that's what you're interested in, take your pick and go with it. If you're looking for something else, the Renesas RL78 and RX series provide a lot of functionality if you're willing to deal with how stodgy Renesas can be.
Some important notes:
1.) Don't bother with Arduino. They were a much more compelling product 15 years ago when you had to pay thousands in tools and compiler/environment licensing to get in on in embedded development. Today, what Arduino nets you is a painfully barren environment that abstracts away a lot of what you're trying to learn when you're starting out. Losing out on the debugging, profiling, tracing, disassembly, memory usage statistics, etc. that modern development environments give you will do nothing but stunt your growth, especially if you're used to having all these tools while writing desktop software
2.) Be careful with (or preferably just avoid) starting with embedded Linux; it's pushing the limits of "embedded". You're going to miss out on a lot of important knowledge and insight jumping straight into using an operating system (and a very heavy one at that), and for many applications, it is MASSIVE overkill. When you start, you're not going to need an RTOS. When you need an RTOS, you're going to reach for something more reasonable, like FreeRTOS. If FreeRTOS doesn't cut it, then you can start looking at Linux.
3.) Don't get tangled up with Raspberry Pis; the microprocessor on these is complex and the documentation is severely lacking/nonexistent. RPis are much closer to a desktop computer than they are an embedded system.
If you really want to get it, I would say one of the most useful exercises is implementing your own microcontroller/processor. You can pick up an FPGA devboard for fairly cheap, and there are plenty of textbooks (Harris & Harris' Digital Design and Computer Architecture comes to mind) that will get you through most of the key concepts. Once you've done this, a lot of the gaps in understanding when dealing with a microcontroller will be filled in. This exercise isn't strictly necessary, but I don't know anybody who has done it that wasn't better off for it.
My final note is to buy or "acquire" Horowitz and Hill's The Art of Electronics. Embedded development is inseparable from electrical engineering, so even if you don't read it front to back, there are some sections that you will definitely be visiting if your background isn't in electronics.