Windshield tint is illegal almost everywhere as far as I know, however I have seen it done well and it is really hard to tell that it is there. It's a good look for some cars, but not my style.
As far as paying extra to go below legal....? why would you? Unless the shop is trying to rip you off I don't see why they would charge more.