I'm trying to figure out whether or not to use sqlite/spatialite on Android with only 29k rows. I just need to find the nearest locations from the user everytime they move outside 100 meters which could be about every 10 minutes. I feel like running querying a spatial database as opposed to looping a collection and calculating distances could be overkill. When is it overkill to use a database in this case?
It's not overkill. It's actually probably required for you to store that data somewhere if you don't want your users to hate the app.
Running a constant process on your phone constantly consumes the phone's system resources. Consuming resources kills phone batteries. People don't like apps that kill their phone batteries. Repeatedly executing queries for that many records to a web service endpoint doesn't seem like the best idea either, since it would eat up your users' data plans. Users tend not to like that either.
29K records in active memory is probably more phone resources than you should be thinking about thinking about consuming unless you are doing something very, very special.
If your data doesn't change though, a database isn't the only way to store and query your data. There might a better solution somewhere in the middle, but I would not expect good results from consuming an unnecessary allotment of users' data plan and/or battery life.