Is smart/fuzzy searching possible in CiviCRM?
This feature exists. It is part of MySQL and called collation. You can read about the background on https://dev.mysql.com/doc/refman/5.7/en/charset-collation-effect.html .

In my test database a search on Nandor returns Nándor. Reason last_name column is defined as

 `last_name` varchar(64) COLLATE utf8_unicode_ci DEFAULT NULL COMMENT 'Last Name.'


and the collation utf8_unicode_ci defines them to be the same.

Altering the setting with

ALTER TABLE civicrm_contact MODIFY last_name varchar(64) COLLATE latin1_bin;


has the effect that they are not considered the same anymore.

What is your collation setting?