Hi Rana, good question! From my Firebase experience, 3 million records is not too big at all, as long as the cost is within reason for you. With Firebase you will be able to access the data from anywhere, including an android app, and implement fine-grained security with JSON rules. The real-time-ness works perfectly. As a fully managed database, Firebase really takes care of everything. The only thing to watch out for is if you need complex query patterns - Firestore (also in the Firebase family) can be a better fit there.
To answer question 2: the right answer will depend on what's most important to you. Algolia is like Firebase is that it is fully-managed, very easy to set up, and has great SDKs for Android. Algolia is really a full-stack search solution in this case, and it is easy to connect with your Firebase data. Bear in mind that Algolia does cost money, so you'll want to make sure the cost is okay for you, but you will save a lot of engineering time and never have to worry about scale. The search-as-you-type performance with Algolia is flawless, as that is a primary aspect of its design. Elasticsearch can store tons of data and has all the flexibility, is hosted for cheap by many cloud services, and has many users. If you haven't done a lot with search before, the learning curve is higher than Algolia for getting the results ranked properly, and there is another learning curve if you want to do the DevOps part yourself. Both are very good platforms for search, Algolia shines when buliding your app is the most important and you don't want to spend many engineering hours, Elasticsearch shines when you have a lot of data and don't mind learning how to run and optimize it.