RE:Access o SQL Server ????
Si lo que vas a realizar es solo una aplicación sencilla con esa cantidad de registros, tanto con Access como con Sql Server podes hacerlo sin problemas.
Ahora, si el volumen de datos va a aumentar con Access vas a ir perdiendo performance en la aplicación proporcionalmente a como crezca el volumen de datos.
Yo te recomiendo que utilices SQL Server, que es en verdad un motor de base de datos, y podes manejar grandes volumenes de datos.
Tenes el MSDE que podes descargarlo de la página de Microsoft de manera gratuita y asimismo distribuirlo a los clientes.
La conexión la haces:
'El ejemplo va con Sql Server, si usas Access debes remplazarlo por OleDb
Imports System.Data.SqlClient
...
Dim con As New SQLConection("cadena de conexión con la base de datos")
Dim adp As New SQLDataAdapter("consulta a la base de datos", con)
Dim dse As DataSet = New Dataset()
adp.Fill(dse, "nombre para la tabla en el DataSet")
'hasta aca ya tenes un dataset lleno con tu consulta a la base
'si quisieras mostrarlo, por ejemplo en un datagrid
datagrid1.DataSource = dse.Tables("nombre de la tabla en el DataSet")
Espero que te sirva.