Bit of a monologue going here, but here is how I solved it.
Previously I purged all SEF URLS and cleared the cache from inside Joomsef. I did this over and over and saw no difference to the URLS even if I turned the setting to include menu names or not.
Because I was testing, I had the SEF features completely off and also joomsef.
After reading the reply, I did the same as usual, but I also went and cleaned the cache in Joomla and purged expired cache. I saw Joomsef 4 was in the list, but it said 0 files.
After doing that, I turned Joomla's SEF on and mod rewrite, as well as activated Joomsef 4.
When I did a CTRL-F5 on the home page, the urls were generated correctly.
I am not sure which of those things I did fixed it, but this may help somebody else.
Thanks for your reply dajo!