There is no globally - one could say even locally - ideal way to deal with missing data. This aspect points to incompleteness in the data you're feeding your algorithms, and imputing is simply a technique meant to fill gaps.
Data imputation's motivation is to make feature distribution in your sets the closest possible to whatever real-world distribution it attempts to portray.
The intuition behind why the median is what worked better for your scenario is not something I could be precise about without having access to the data you worked upon, but the positive result is deeply related to your feature distribution, which for the missing points in your data is better represented by the feature's median than all other metrics you've calculated. I'd recommend reading material such as this article that both explains and shows implementation of different imputation techniques - KNN, as you mentioned, being one of them. One of the advantages is seeing how different methods work for a given distribution:
As you have already pointed in the end of your question, methods such as KNN are some straightforward means of imputation that could benefit your case better than mean/median imputation. The biggest difference between those is that KNN better preserves the variance in your data, whereas mean imputation (as you can see from the above image) shifts missing data towards a single value.
Since no method is 100% globally optimal, I'd advise you to try them - KNN, Multiple Interpolation and the likes - and compare. Invest the appropriate amount of time on the techniques that make the most sense for your data.
