Which Node type is better for SEO? Page or Story?

No. Why should any search engine make a difference?

You should use URL aliases instead of the node/nn links, but that's all.

There is no difference. Page and Story are just two default content types in Drupal to start you off, and you can even skip using them altogether if you prefer (the only real difference besides the name is that a Story by default has the "Promoted to front page" option checked, whereas a Page is the same exact thing, but with that option turned off by default). Some people use Page type for pages of the site that are static basic-information types of pages (e.g. About, Site information, etc), while they use Story for short-term content such as news, blog-like posts, etc and show a listing of those on the home page (though Drupal can display home pages in many other ways). In fact you are not at all limited to Page and Story and can (and in many cases "should") add as many custom content types as you want, to suit the needs of your site. If you add CCK module you can also add as many custom fields to your content types as you want, which allows you to collect the exact data for each node that you need, and also allows you to use each piece of data individually in a wide variety of ways, both in your node templates as well as through modules like Views.

For instance suppose hypothetically every page in your "Past Clients" section of your site (just an example) should include a photo or company logo, the date the project was completed, the name of the company it was for, the name of the city/state the company is located in, etc. With Drupal's CCK, you can add those fields so that whenever you make a "Past Client" page, it will ask you to fill those exact fields in (or your employees adding content to the site for instance, who might not remember every piece of data that needs to be on a Past Client page otherwise). After filling in the form, Drupal displays all of these details in the exact format you predetermine in your template, rather than you having to format it each time with your own HTML. This is something that sets Drupal's abilities over most (if not all) other CMS platforms, as you can harness all that customizable functionality with little to no programming at all.

For improved SEO, the modules you need most are Pathauto and Global Redirect.

-- David
davidnewkerk.com | absolutecross.com
View my Drupal lessons & guides