Why don’t ‘wp_nav_menu’ CSS classes work until a menu is created?

This is due to the wp_nav_menu parameter fallback_cb:

If the menu doesn’t exist, a callback function will fire. Default is ‘wp_page_menu’. Set to false for no fallback.

You have not specified an alternative, so it uses the default, wp_page_menu.

You could create your own function to display a page menu with the proper markup, or set the fallback_cb parameter to false and display nothing.

has_nav_menu might also be helpful for displaying alternate markup when a menu isn’t available.