Vice as a usable package doesn’t comply with Debian’s distribution policy. As Cloanto (and likely others) claim ownership of the Commodore IP, Debian can’t distribute the ROMs that make the package work. The source code to Vice is GPL v2 (hence the Vice Hall of Shame), but the ROM distribution situation is explained in Debian’s README.ROMs:
The ROM images for the 8-bit components required to make VICE are copyrighted, and you install them at your own legal risk. Tulip Computers, in the Netherlands, appears to hold the copyright to them, and is being somewhat persnickety about who uses them. You will have to get your ROMs somewhere other than this package.
But the most authentic source of the ROMs is the VICE source package itself, under the data/ directory. It can be downloaded from http://vice-emu.sourceforge.net/ .
Laszlo Boszormenyi (GCS) 2017.12.04
The Commodore IP situation really makes distributing a working emulator almost impossible as free software. Other legacy systems are not so badly affected:
openMSX comes with the BSD-licensed cbios BIOS rewrite. It’s minimally useful, but will allow some MSX software to work.
fuse, the ZX Spectrum emulator, can use either the free but only mostly-compatible opense-basic ROM, or the non-free spectrum-roms which were blessed by Amstrad for release. Sinclair and Amstrad never held the source to the ROMs (it’s complicated, but seemed cheaper at the time) so the original images can’t be “free” to everyone’s satisfaction.
It’s a pain, and every time I upgrade I feel that “Debian broke Vice!”, but it’s all part of the sorry Commodore IP mess.
Well, dealing with copyrighted ROMs is just par for the course with emulators. The issue here is that VICE 3.5 altered the location of where it expects the ROMs, so your first google hit for “install VICE linux” tells you the wrong place to put them.
I don’t blame the VICE developers, though. The new location does make more logical sense than the old location.