The Options API is primarily a database API, allowing you to get and store values in the options table of the database easily.
The Settings API is an interface API. It allows you to build settings screens in a manner that will adapt with future changes to the WordPress interface, as well as to handle security (nonces and whitelisting and validation and such) automatically and more easily than rolling-your-own-code.
More on Settings API: http://ottopress.com/2009/wordpress-settings-api-tutorial/