I know it's possible to play around with Access files on UNIX systems, but you have to install/config some kind of ODBC enviornment.
You're correct. A quick search on Google turned up several possible ODBC drivers for Unix. On Windows this is a great solution because the Jet engine works quite well and you have the "one file" convenience of the MDB (Access) file. Keep in mind that even on Windows, your program isn't talking to the file directly, it's talking to a full-featured data base server (Jet or MSDE) via ODBC. However, with this solution on Unix, you'd still need a Windows server to host the Jet engine and the Access/MDB file. Probably not what you want. As mentioned here, I think AnyData or XBase would be your best bet. If your data set is going to be large and search time is important then you may need to bite the bullet and go with a "real" DB server to get the performance you need.