How big are your databases? I imagine they aren't that big if you can use Access for them. Most of the companies I have worked for had to use SQL Server or Oracle due to shear size and reliability concerns.
It would be a bit of a hassle but you could probably switch to Filemaker as it is cross-platform, has been around forever, and works great. I know it would be annoying to have to learn a different program, and convert existing records, but as you say, your Windows machines are annoying too. You could download the 30 day trial to see if this might work for you.
I haven't tried the database in NeoOffice but you might download that and see if it converts your databases over well. My experience with documents, spreadsheets, and presentations has been pretty solid so far with this suite. And as others have said, you can beat free.
Also, I hear MySQL is nice too. Here are some links to get you started:
Filemaker Pro Trial
Neo Office Download Page
MySQL Dowload Page