Yes, getting fired sucks if you're on an H1B but your comment doesn't apply to job changers generally. H1B visas are transferable (with a little paperwork) so an employee looking to move jobs just needs to ensure that they have their ducks lined up and that any required paper work is filed - usually that means lighting a fire under the HR team of the new employer to make sure it doesn't slip through the cracks.
1. You can start working for the new employer as soon as the petition has been sent out. For example, as soon as you have a FedEx/UPS tracking number for the petition, you can start the new job (even before receiving a Notice of Receipt).
2. You get a Notice of Receipt (form I-797C) usually in less than a week (and usually in about 3 days), if the petition was mailed in with overnight shipping.
3. Now receiving a Notice of Approval (form I-797A or I-797B) -- i.e. the actual adjudication of the petition, typically takes a couple of months with regular processing, but only 15 business days with premium processing.