It depends on the browser and which cookies they delete.
If the user deletes all cookies, yes, they will be considered a new visitor when they return after deleting their cookies.
If the user deletes just the AMCV cookie or all cookies on your domain things get a bit more complicated. In this scenario Firefox and Chrome would result in the same visitor whereas Safari would be a new visitor. This has to do with the way the 'MID' value within the AMCV cookie is calculated. If possible it will use a third-party demdex.net cookie to calculate the MID. In Safari this third-party cookie is blocked so it is unable to recalculate the same MID value.
I've put out a few videos about how the Experience Cloud ID Service (formerly Marketing Cloud ID Service) works on our community YouTube channel. You can view these videos here.