Rumbaさん、こんにちは。

＞えと、方針だけは既に決まっていて、テーブルの再構築とＰＧの再作成をすることになっています
＞なので、ハードウェアには変更なしなんです
＞社内LANでの使用は問題ないとのことなので、社外からのPHS接続と支社からのINS64接続が問題なんです

DBのチューニングは、DB管理者とよく話し合ったほうがいいと思います。
DBの正規化を基本としたとしても、検索系にばりばりの正規化を行うと
思わぬレスポンスの悪化になったりする場合があるし、DBMSが推奨している
チューニングの方法もあります。
また、インデックスの使用状況などもきちんと把握しないととんでもない目に合います。
この辺は、IT Proってサイトで事例集とかが載っているので探してみるといいでしょう。
（多分、DBのチューニング関係は、DBマガジンとかの雑誌に載ってるよ）