For your Medicals, there are a few options:
For those in Lagos
- Qlife family Clinic is in victoria island, off ajose adeogun.It also happens to be the cheapest option
- IOM (International Organisation for Migration) is in GRA Ikeja, there is also a branch in Abuja
For Police Clearance, you can easily walk into Alagbon at Obalende. Minimum is about 4k