To get the Gog version of HOMAM to run on linux without that silly "No CD" error, just follow these simple steps:
1. Install GOG version of HOMAM. If you are using WINE to do this, the default install directory should be something like /home/<user>/.wine/drive_c/Program Files/GOG.com/Heroes of Might and Magic/
2. Copy the HOMAM directory. I copied it to an easier directory to handle in terminal, like /home/<user>/games/homam/
3. Install dosbox. If you are using an apt-get system, simply type in sudo apt-get install dosbox into the terminal. If not, go online and find it!
4. Open terminal. Go into the Heroes directory:
cd /home/<user>/games/homam/
5. Run dosbox with the gog conf parameter:
in terminal, type: dosbox -conf dosboxHOMM1.conf -noconsole
and press enter
The game should now run, simple as that!
Credit for this guide goes primarily to Horus, who wrote an extremely similar guide for the Mac OSX

I just got Heroes II from here. I got it running in wine 1.1.26 on Fedora 11 KDE by
1) Adding the gogwrap.exe as an application.
2) Setting appropriate sound driver for your system. (I use Pulseaudio, Full Hardware Acceleration, No Emulation
3) Find dosboxhomm2.conf in your installation folder and open it.
4) Set "output" option to opengl so the line looks like output=opengl
This has it working perfectly for me, including in game music. You can mess with resolution and various other video and sound options in the same conf file.

I think you're better off using this guide and using the native Linux DosBox. ;)

I bought this from GOG on 21 August 2014, and the instructions no longer work. I get stuck at the cd error. Poking around the conf files I've found a simple solution:

1. Follow the steps #1, #2, and #3 above as usual

2. Open terminal and run dosbox
dosbox

3. Mount the directory where you have Heroes 1 and change the drive (specify your own directory):
mount c: /home/b0rsuk/Gry/dosbox/H1
c:

4. Mount the cd image:
imgmount homm1.gog -t iso

5. Run the game:
heroes

This is for Dosbox 0.74 on Debian Linux (Jessie)