For anyone experiencing the same - DNN Support evaluated and noted that if you set a default theme on your site, then delete the folder, your theme menu will indeed disappear. You can run a SQL line to reset the default them to an existing theme, but you have to know that you've deleted that folder in order to search/update.
Now that we know, GREAT, we can plan to use a default theme on sites that won't be deleted by super users OR admins (our clients are usually given admin roles but are not typically savvy enough to handle that responsibility, but I digress). However, this disappearing menu as a result of an easy thing to do (deleting a theme is easy, after all) seems like kind of a pothole that could be addressed on future updates.
Thanks all for helping narrow down and find the problem!