At capacity, without abiding by the 80% rule, a 20A circuit can provide 240*20=4800W. But, most of them (all?) require derating to 80%. 3800W would work IF your supply was really 240vac, but because it often isn't, 3500W is safer. You really need to read the installation instructions for one you might be considering. Otherwise, if your voltage was low one day, you'd end up tripping the breaker. That is most likely to happen during a hot spell when everyone has the a/c cranked up, and the main supply is being heavily loaded...the voltage tends to drop under those circumstances.
As the available wattage increases, on the same size tank, your first hour draw will increase. To get the same draw, you could go with a larger tank. The idea is that most people don't use max hot water constantly throughout the day, so even with a smaller wattage unit (if the tank volume is large enough), you will have enough time for it to recover by the next time you need a large quantity of hot water. If you're now running out of hot water, without changing the wiring, you need a larger tank while keeping the wattage the same. It will just take longer to reheat, just like the difference with boiling a 5qt pot verses an 8qt one.