Tiling under cabinets: if you've already got them out and not afraid to spend the money...then why not? Alot of people don't because it's inconvenient. As long as you can still get everything under the cabinet with no problem then it really is up to you. I would try to make it accessible so that 5 or 10 years from now I could replace the dishwasher with no problem.
Underlayment: for very thin areas use self-leveling floor leveler. Read the information on the bag for recommendations. For deep places, fill in with "other stuff" whether with plywood, planks, or concrete. For tile you should use some type of backerboard/concrete board. For carpet...just keep it reasonably smooth. Padding will take up the slack. For hardwood (and "fake" hardwood) follow the manufacturers recommendations. For roll flooring (vinyl, linoleum, etc) minimize cracks... I frequently cover floor with 1/4" luan for a smooth surface and fill the cracks with drywall mud sanded smooth...before laying stick on tile or vinyl flooring. If you have to build up one floor to match the elevation of the other (which has a different flooring material), install the highest first then bring the next level up to it with an appropriate material such as OSB or CDX plywood. In high moisture areas use the preservative treated materials.