Why are my queries taking so long?
I have some theories as to why the performance is so bad. 


Lets see.


  The first is that I simply have too many rows. 


Probably not. There is no limit on the number of rows in a (SQL) DBMS. 80 million rows is not that much these days.


  The second is that a database is not suited for this task. 


Unlikely. We don't know which DBMS you use (Postgres? MySQL? SQLite? SQL Server? There are hundreds of them) but I think any of them could handle what seems to be a simple query.


  The third is that my query is not well formulated.


No, it seems good. The query produced will look like:

SELECT id, firstid, secondid, ..., distanceValue
FROM LocationsLookupTable
WHERE firstId = ?
  AND secondId = ? ;



  So, what is causing this?


If that is all the code that is creating the table, then what is missing is indexes. Lacking them, the database optimizer/planner has to create a query plan that scans the entire table. While the table is not big, it is not very small either. 

Adding an index on (firstid, secondid) will improve performance a lot.

However 300 seconds looks too long, even for a table scan, so the hardware or the DBMS settings should be examined, too.