Try running SimCityRecovery.exe - the default location (for 64 bit machines) is Program Files (x86)\Origin Games\SimCity\SimCityRecovery. Right-click SimCityRecovery.exe and choose "Run As Administrator". Be patient, it can take a while to run. Set your desktop icons for Origin and SimCity to "Run As Administrator" and try the game again.
This error message is talking about video memory allocation, not hard drive space or RAM. If SimCityRecovery doesn't help, reply back with more information about your setup. What OS are you using, what video card, are you using the latest drivers for your video card (or did the issue start after you upgraded your drivers?). Lowering your settings options might help if you're running at highest settings. Also, the game was built before 4k and may not support those higher-end monitor resolutions well. It might just take some fiddling around with your display and graphics settings to find the right ones for your setup.