PHPとMYSQLで文字化けで困っています。

MySQLがUTF8がデフォルトになっている環境で、EUC-JPでPHPコードを書いている、すなわちクエリをEUC-JPで渡すので文字化けするわけですが、SET NAMES ujisを投げると、UTF8環境に対して、「EUCで書いたクエリを投げます」と事前に言っているので通るわけです。
そうして、MySQLデータベースにEUC-JPで保存されているデータを、レンタルサーバーのデフォルトでUTF-8で表示させるので化けて見えるのです。
phpMyAdminの文字コードをEUC-JP(ujis_japanese_ci)に切り替える事で文字化けを回避するという手もありますが、とにかく全体で文字コードを統一させるのがベストです。ではEUC-JPとutf8のどちらに統一すべきかと言えば昨今の主流はutf8だと思います。

それはそれとして、SET NAMES ujisを毎回投げるのが面倒なら、クエリを投げる処理を関数として作って、その中にSET NAMES ujisコマンドを書いておくというのもひとつの手ですが、それよりも、レンタルサーバーのデフォルトに合わせて、PHPもutf8で書くことをお勧めします。

DBの文字セットを確認してください。