Using wine 20040716 (the version of wine currently in debian unstable) I was able to install GTA3 with no problems.It was a simple case of (this also works in wine 1.0.0 perfectly):
1) Mounting the install CD
2) Doing wine /path/to/cdrom/Setup.exe
3) Follow on screen insructions

To play the game once installed:
1) Change to install directory
2) Insert and mount play CD
3) Doing wine gta3.exe
4) When the screen goes black click the left mouse button twice (or press Return twice) to bring up the game loading screen.
5) As long as you have no problems you should be playing the game.

To patch the game to version 1.1:
1) Download the patch
2) place it in the install directory
3) Do wine patchname.exe
4) Follow on screen instructions

A few issues I noticed:
1) The mouse is dodgy on the menus. It continually jumps to the middle of the screen.(but that doesn't matter too much the arrow keys work just as well)
2) The intro movie was jerky, but then again I think it was when I ran it in windows too.
*3) Areas with a lot of sound activity going on can cause the game to crash (the getaway from the bank job is one such instance). A partial workaround is to reduce the value of the following two lines in $HOME/.wine/config :

"SndQueueMax" = "12"

"SndQueueMin" = "8"

*This is somewhat outdated and doesn't seem to be a problem anymore. Plus they have done away with the wine config file.

Fix to 360 mouse problem.

I also found a problem with being unable to look past 180 and sometimes 270 degrees with the mouse. (bug 6971)

To fix the mouse problem, you need to apply a patch to the source code. You can find the source code to download here: http://sourceforge.net/project/showfiles.php?group_id=6241&package_id=77449 Just download it, and extract it. To do this, run this command from the directory where you downloaded the wine source:

tar jxpf wine-*version*.tar.bz2

Now you need to apply the patch, you can find the patch here: http://bugs.winehq.org/attachment.cgi?id=13153 Save that as "hack.diff", and place it in the source directory (the directory that was extracted when you extracted wine). Next, run this command:

patch -p0 <./hack.diff

Then run both of these commands (assuming that you have all of the dependencies needed, you can just run "sudo apt-get build-dep wine" in Ubuntu to get all of the dependencies.):

./configure

make depend && make && sudo make install

Finally to apply this patch you need to add the following to the executable:

env WINEFORCEMOUSEWARP=yes

It should look something like this in the application launcher:

env WINEFORCEMOUSEWARP=yes WINEPREFIX="/home/user/.wine" wine "C:\Program Files\Rockstar Games\GTAIII\gta3.exe"

Or you can just run it in the terminal from your GTA III directory by running this command:

WINEFORCEMOUSEWARP=yes wine gta3.exe

That should fix the mouse look problem!

It also seemed to me that the games motion blur was not rendered properly in game by wine nor does it look good, so it might be a good idea to switch off the option Blur FX in game.

I modified the previous maintainers howto so the first two parts are his while the last parts are mine.