You sound like me from last month. I strongly recommend silverbullet, check it out on https://silverbullet.md
Can be selfhosted
Check, even has a simple docker compose
Stores the notes as plain text or *.md files, not some SQL database.
Check, it does have an SQL database, but it's used for queries, you can even copy or modify MD files at will
Can use Marddown format.
Check, it's a superset of markdown that includes queries for cool stuff like create tables that group data from other pages
Have an android client or at least a mobile optimized web-interface.
Check, it has a PWA that works offline and syncs when back online. Note that this means that all files will be on your device if you use it like that, but that's expected.
Not a must but it would be nice to have a to-do list option.
Check, like I mentioned you can query all tasks on all pages and even do filters based on several factors, like where the task is defined or extra attributes that you set to them, e.g. priority.