There are a couple factors to replacing the cabinets/countertop: Where is the existing plumbing, and is there tile underneath? Depending on those, it will help guide to what the cabinets should be replaced with.
Tile
If the tile doesn't extend all the way underneath, I'd be sure the new cabinets covered any untiled areas (unless you are replacing tile as well). You could probably remove the toe kick to check, if you can't see from somewhere else.
Tile is nearly impossible to "add to". If you're super lucky, maybe you have some of the same tile and grout left over and it would be possible to add and have it not look completely different. More often, it's impossible to find an exact match, and so the only way to make it look right is to completely replace all tiles.
Plumbing
I'd also ensure they were big enough and positioned so the plumbing wouldn't have to be changed. It's not impossible to change plumbing of course, but moving it even a few inches could add anywhere from a couple hours of work, up to a multi-day job that includes re-tiling the entire floor (if you have to open the sub-floor and break tiles to do it).
As long as you have a couple inches between where the plumbing comes in to either side of the cabinet, it's doable. You just need enough room to actually work on the pipes.
So to answer your direct questions:
Leave as much space as you feel looks okay in the space, which could be as little as none (like it is now).
I'd tend towards finding something that is big enough that prevented me from re-tiling the floor, and from moving any plumbing. It would take a lot to convince me personally to change to a vanity that required those types of changes, assuming they weren't happening anyway. Most of the time as far as the look goes, it would be possible to find a similar looking vanity that is slightly wider/has a closed-in base/etc, so the design is essentially the same but extra work and expense is avoided.