It wouldn't be honest to only quote with-testing and force them to pay for something they may (mistakenly or not) not want.

Your customer isn't paying for the code you write, they are paying for a finished product that works. How much code you write should be irrelevant to them.

In fact, one could argue it is far more dishonest to quote without testing since that does not include the maintenance costs that will be incurred by them after the initial product delivery, which will almost certainly be higher than a project with automated tests.

I completely disagree; you're quoting them the number of hours it will take you complete their project with the understanding that it will be at a certain level of quality. As long as you're both on the same page as to the expected quality, how you get to that point is your problem, not the client's. When you bill hours, you do include any time spent sketching some design, or debugging some problem, right? How is ensuring quality in a different fashion and including that time in your quote dishonest?

Yep, you're right.

I would argue it's the same as trying to quote separately for debugging. You could take the approach that the unit tests are part of the implementation, but integration tests can be billed separately.