Welcome to the forum!
You could of course put every contact in a new note with E2EE turned on, but I can't see a way to integrate contact information with other apps in a meaningful way (such as phone or mail apps).
If I understand you correctly, it would be the best solution to self-host a Nextcloud server and access your contacts via CardDAV on your phone using Android apps such as DAVx5.
Edit: just read your last sentence - that seems to be tricky indeed. Proton Mail and Tutanota offer something of that kind (as you mentioned), but encrypted (and fully functional) contact info seem to be a difficult issue even for privacy-oriented services like these.