An ideal search site would have one input box and a submit box. And maybe the logo too :D After the data is input, the design that comes to my mind again is the linear results displayed by most search engines (except cuil). This is the part where you can make a difference. If you don't mind about the business model (or in specific ads) currently, then use the space on the right side too. Use it to display thumbnails of the page. And along with the common search data shown by other search engines, you could also display data about the media in the page and even the type of page(flash or html etc). Any medi in the page like mpg, wmv, asx etc can be mentioned in the results. Coz if a person is searching for just test then that can be useful.
Also the thumbnails data I mentioned are of much use when doing quick surfing. I wouldnt want to endup on some page that isn't readable.