自分も昨日から背景を検索してたけど、
640x480サイズが多いね。こことかも。
　ttp://masato.ciao.jp/haikei/furemu.html

で、試しに「Yukari」ってリサイズツールで
640x480→800×600に拡大したら、
劣化が気にならない程度だったから、
サイズは気にしなくてもいいと思う。
　ttp://omoikane.my-sv.net/soft.htm

拡大背景＋キャラ乗せ見本。
背景は↑の「背景イラスト 家・部屋」から。
　ttp://hirame.vip2ch.com/up/hirame000120.jpg