The core of this issue has been fixed (on 2019-10-06) in MikTeX, but since the situation involves formats and is overall a bit tricky I wrote up a guide at https://github.com/MiKTeX/miktex-packaging/issues/131 explaining (roughly) what is happening here and what you can do if you are still suffering from this issue. This is copied pretty much verbatim from over there.
OK, this turned out to be quite a tricky issue, since there are several things at play here.
The heart of the issue: Incompatible packages
The core of the issue was as follows. The LaTeX development team released an update of the LaTeX kernel (LaTeX base in ltxbase) along with several core packages (e.g. graphics, graphicx, amsmath). The updated core packages are intended to work with the updated LaTeX kernel and some need the correct version to function properly. Among these core packages was graphics/graphicx.
The packages and the kernel were uploaded to CTAN at almost the same time and arrived in TeX live with the same sweep of updates. Due to unfortunate timing, only graphics was updated in MikTeX leaving the LaTeX kernel on an older version. Using the graphicx package with the older kernel causes the error messages described in https://github.com/MiKTeX/miktex-packaging/issues/132, https://github.com/MiKTeX/miktex-packaging/issues/133 and here (as well as linked questions and duplicates).
The core issue of the MikTeX package server distributing incompatible packages was fixed swiftly the next day on 2019-10-06 (UTC). Since then the server has distributed the newest LaTeX base package (2019-10-01) that matches graphics.
The LaTeX kernel is special
Usually when a package is updated it is enough to renew the file name database to tell TeX about the addition or removal of files. This happens automatically when the MikTeX Console is used to update or install packages (same for TeX live's tlmgr and friends) so the average user will not have to worry about that.
But the LaTeX kernel is special. It defines a TeX format and is directly baked into the executable so that all LaTeX commands are available from the start without loading any packages (the LaTeX commands can be used without any \usepackage directly from the start). This means that it is not enough to renew the file name database when the kernel was updated: the formats also need to be regenerated and baked into the executables. Again this should happen automatically when the MikTeX Console is used to update the LaTeX kernel package.
OK, so what can I do?
Update in Admin and User mode
First of all you need to make sure that your MikTeX system is fully up to date. Run an update (see https://tex.stackexchange.com/a/55473/35864). If you have a multi-user MikTeX make sure to run the Update in User and Admin mode.
Double check that lxtbase is up to date by going to the Packages tab in the MikTeX Console and searching for ltxbase. The install date should be 2019-10-06 or later and the packaged date 2019-10-05. If you have a multi-user MikTeX install, the package may only be installed in one of the two modes. You do not have to click install in the other mode, you just have to make sure that it is up to date when it is installed.
In an ideal world that should be it. The formats should automatically be generated as needed during the update and things should work.
Small aside: The admin–user distinction is a common source of problems in MikTeX. The updater will always only update the packages installed with its permission level. If you have a multi-user installation and installed packages with User-level as well as Admin-level permissions, packages may get out of sync if you only update with one permission level. Whenever you encounter an update-related issue always make sure to update your system in Admin and User mode, often that makes issues go away. (Of course this only applies to multi-user MikTeX installs.)
Check your format
You can check your LaTeX format by running a simple LaTeX document like
\documentclass{article}
\begin{document}
Lorem
\end{document}
Open the resulting .log file and check out the first few lines
This is pdfTeX, Version 3.14159265-2.6-1.40.20 (MiKTeX 2.9.7200 64-bit) (preloaded format=pdflatex 2019.10.12) 12 OCT 2019 11:42
entering extended mode
**./formatdate.tex
(formatdate.tex
LaTeX2e <2019-10-01>
("C:\Program Files\MiKTeX 2.9\tex/latex/base\article.cls"
Document Class: article 2019/08/27 v1.4j Standard LaTeX document class
The important bit is the
LaTeX2e <2019-10-01>
the date should be 2019-10-01 or above.
The date in the preloaded format=pdflatex 2019.10.12 in the very first line should show a date after 2019-10-06.
You can use the command
kpsewhich --engine=pdftex pdflatex.fmt
from the terminal to find out where your format resides. The folder may give you a hint whether or not you are dealing with a User- or Admin-controlled format. This is important for the next step. If it is C:/Users/<User>/AppData/Local/MiKTeX/2.9/miktex/data/le/pdftex/pdflatex.fmt the format is user-controlled, if the format resides in C:/ProgramData/MiKTeX/2.9/miktex/data/le/pdftex/pdflatex.fmt we're talking about an Admin-controlled format. If the file path looks nothing like the two examples it may well be that you have a spurious format spooking around somewhere.
Recreate the formats
If your formats are not new enough, MikTeX either did not recreate the format during the update or it did recreate the formats, but still picks up older versions of the formats.
You can rebuild the TeX formats as described in MiKTeX: Error After Update: "Sorry, but pdflatex did not succeed.". You will need to rebuild all the formats you want to use (probably at least pdflatex, latex, xelatex, lualatex). It may be possible to simply select all formats and rebuild them, but some formats may produce errors on rebuild. In that case you may need to hand-pick the formats you need.
Again if you have a multi-user installation there might be a need to do this in Admin and User mode. Generally I recommend to rebuild the formats in Admin mode first (if you have Admin rights that is) and only then if still necessary in User mode.
In case the relevant formats create error you can not resolve or understand on rebuilding, ask a question on your favourite TeX forum and give enough details so people understand what you did.
If you rebuilt the formats and still MikTeX doesn't pick up the correct formats, your MikTeX might be misconfigured. This is then going to be a specific issue that can only be diagnosed with more detailed information about your system. Again it might be better to ask a question with as much detail as possible on your favourite TeX forum.
Last comments
The fix from Joseph's answer is intended to be a temporary workaround. It should not be needed any more since the correct kernel version is now available in MikTeX. Please don't use this workaround any more. Instead make sure that you format gets updated correctly.
If you want to know more about TeX formats, LaTeX etc., have a look at http://www.tug.org/levels.html and What is the difference between TeX and LaTeX?. Overleaf has a nice article on formats at https://www.overleaf.com/learn/latex/Articles/The_two_modes_of_TeX_engines:_INI_mode_and_production_mode.
Incidentally new installers and the like will probably not help here, since this is purely an issue related to things that happen after installation. Indeed it may not even help to remove MikTeX and install a new version if problematic files remain in directories not controlled by MikTeX. It is therefore important to try and understand where the problem comes from before going on an uninstall-reinstall spree.
MacTeX
As it turns out there is a related issue in MacTeX (which is based on TeX live and not on MikTeX): \includegraphics broken on MacTeX 2019?. Updates in MacTeX don't trigger format rebuilding, which means that even though all packages are up to date one might be stuck with an older LaTeX format. In that case
fmtutil-sys --all
should help fix the issue.
A more detailed discussion about why that is necessary is at https://tug.org/pipermail/tex-live/2019-October/044119.html.
