Is the language server supposed to analyze in background for several minutes every time I open VS Code?
Every time I open a project it starts analyzing thousands of items for several minutes. I have only recently noticed this behavior and was wondering if it was normal.

It depends heavily on what you have imported and what is installed in your environment. The old version of the language server likely also was running in the background, the difference is that the new language server reports progress (so this is more visible). See also #832 (particularly https://github.com/Microsoft/python-language-server/issues/832#issuecomment-477688703).
Regarding "every time I open VS Code", yes, the LS does not persist its analysis (that's #472).
There are some other performance bugs we're working on as well, particularly one that for some libraries makes the LS enter essentially a busy loop for a good amount of time. But, a few minutes isn't unexpected at this point.
Analysis at startup is expected, there is no persistent database or anything along these lines yet. We have several items open related to caching, so closing this one.