I think new readers should start with Mistborn or Stormlight, mainly because I think those are his strongest works. The first Mistborn novel is good because it is relatively short, self-contained to a reasonable degree (it doesn't leave off with huge cliffhangers or anything like that if I recall correctly), and it shows off a lot of Brandon's signature style pretty early on.
For readers who like long works and are perfectly happy to start a big one, WoK is the best place to start. It has the best world building, the most interesting characters, and is just overall the best thing so far as long as you don't mind the length.
I think the stories are set up so that you don't really need cosmere stuff for them to make sense, and I don't think new readers need to care about the cosmere stuff at all. I just think they should hop in at the most compelling stories.