Well I knew it was too good to last. After I formatted my drives and did a clean install of Windows 10 and installed all my tons of software the "NEW" menu still popped up instantly with no delay. Today to my surprise it was non functioning as before. I was to say the least PISSED.
Luckily I knew that I had only installed 2 things recently. One was ITunes and another was some APP I installed from Microsoft Store that opens Excel files. I uninstalled both. As well as uninstalling ITunes I also uninstalled the apple device manager and software updater since those have to be uninstalled separately. I checked the "NEW" submenu and to my surprise it worked perfectly again. No delay. I didn't even have a need to reboot.
So, in conclusion. It was abundantly clear the issue is in direct relation to some APP or software that is causing an issue with the menu or shellex associations. My wife had neither of the 2 programs that I had installed so hers is more than likely being caused by a different APP. My suggestion than to those who are experiencing this problem. Uninstall your apps one by one to see if the problem is resolved. If it doesn't get resolved you can rule the APP out and reinstall it. There is no need to uninstall software that you have used for years but if it isn't something you have used frequently it may be the cause.