What are some common personal care products I can use that minimize toxic chemicals and plastic (or all) packaging?
Many people, including myself, swear by castile soap such as Dr. Bronners. You can purchase it in bulk, and it has many uses other than just in washing your skin. It's one of those versatile things like baking soda and vinegar which have dozens of uses.
A plastic-free alternative is a bar soap, I like the Kiss Your Face pure olive oil soap because it has a paper wrap and the only two ingredients are saponified olive oil and salt. You can also buy rather large bars (more product per packaging). Many stores sell bulk soap (such as some Whole Foods, natural food stores and co-ops) but you probably have to be careful about reading the ingredients.
If you are ambitious you could probably make your own soap, which is best left for somebody with experience to answer.
Shampoo and conditioner can be completely eliminated in favor of castile soap (such as Dr. Bronners) or the "no poo" method, which uses baking soda as a shampoo and dilute vinegar as a conditioning rinse. Personally I have used the "no poo" method for several years and get comments about how great my hair looks, and I think it feels and looks amazing. There are many resources for the "no poo" method (just do a Google search and you will get a ton of hits) but here is a good blog post with an explanation.
Coloring of hair can be done with henna, this great blog post on My Plastic-free Life shows a couple henna methods (buying henna in bulk, and using a henna bar from Lush).
I'm hoping somebody else can comment on other hair products, which I tend not to use. I have seen many recipes for flax hair gel but I'm not sure what is used to replace hair spray, although this post suggests using sugar or sea salt mixed with water.
This has been touched on in another post on this forum. To sum up: baking soda works miracles!
It can be difficult to find an eco-friendly toothbrush, which was highlighted in this great post on My Plastic-free life. I like the Preserve recycled toothbrushes because they are so easy to find, easy to recycle and don't cost a lot of money.
For toothpaste, you can make a tooth powder using baking soda, salt and cinnamon (just Google for tooth powder recipes). However, I have heard this is bad for your gums as it's very abrasive and I've stopped using it. This post on My Plastic-free life goes over a ton of homemade toothpastes and other alternatives.
As far as dental floss goes, I like eco dent floss which comes with only minimal plastic in the package (to keep the floss fresh). The floss has no teflon coating yet is still very good at gliding between the teeth.
I have yet to find the best floss alternative for teeth that can't be flossed conventionally (for those of us with braces or a permanent retainer), but super floss (or the drugstore no-name brand) has minimal plastic in the packaging at least. If you found a good, reusable floss threader that would also be an option, although I find them to be very bulky (i.e. hard to fit between my teeth) and very cheap/disposable.
Face / Makeup
Face washing can be accomplished with castile soap (such as Dr. Bronners), some people suggest using the tea tree version of Bronners or adding a few drops of tea tree oil to your favorite castile soap. A lot of people swear that using castile soap has cured their acne problems, but I would take that with a grain of salt as it doesn't work for severe acne. I also like Desert Essence face wash, although it does come in a plastic container you can find it in quart sized bottles which lasts a very long time.
I enjoy Organic Essence lip balm which comes in a biodegradable container and has all USDA organic certified ingredients.
Hopefully somebody else can comment on makeup, as I haven't phased out my collection to anything approaching sustainable as of yet. I know there are a lot of organic makeup brands out there, but I can't vouch for their actual sustainability or quality.
For shaving, I absolutely love my Merkur safety razor. I had a no name brand safety razor for a while, until the screw on the head broke off and I couldn't get it fixed. The good thing with Merkur is that I've heard they will fix them if they break.
The blades are stainless steel and if you don't have coarse hair, can last a very long time. I have a package of Lord safety razor blades (for example, on Amazon) that came with no plastic in the packaging. I haven't even used up one small container of 5 in the couple of years I've been using the Merkur razor, so a package of 100 will probably last a long time.
If you are adventurous enough you could try a straight razor.
I have found that I don't' miss shaving cream at all, I simply use liquid castile soap or lather with my bar soap.
Tweezing is of course another alternative which doesn't require using any products other than a pair of tweezers.
Organic Essence has some great lotions which come in compostable containers and are made with USDA organic ingredients. I've had my lotion for probably 1-2 years now, and I must admit that the packaging is not in the best shape but has still held up. If you go through lotion quicker than me, it won't be a problem and you can put all of the packaging in your compost bin when you're finished.
There are also some lotions (such as this, or do a search on Etsy) that you can find packaged in aluminum tins.
If you cook with olive oil, I find I like rubbing some in on my hands, although it does leave your hands very greasy.
Short simple answer is to learn to make the products yourself from all natural products that you grow (as much as is reasonable) yourself. However that is a tall order but many a (sustainable) cottage industry has started this way.