Before designing any debounce hardware/software check the bouncing characteritics of the push button. Checking the button every 1ms as someone suggested is total overkill. Most buttons work well with 20 to 30ms, i.e. the bouncing happens within that timeframe, but there are also some buttons which require a longer delay. Waiting 500ms might prevent pressed-by-mistake situations but gives a bad feedback to the user .
I agree with all of that, especially the part about making your debounce technique fit the button.
But the idea of waiting to process a button got my attention.
Usually, with a typical normally open push button, if it has been "open" for a long time, and then you register a "closed" condition, even for a microsecond, you can be absolutely sure the button was pressed. There's no need to wait at all to start processing the button. However, you want to wait some time period for things to settle down before you start interpreting subsequent openings and closings as genuine.
But the reverse isn't true. If the button has been closed for a while, a detected opening should probably remain open for some time before you interpret it as a real opening, and not just a glitch in the contacts.