What is the best way to theme the first row in the view differently?
In this specific situation, the issue can be easily solved by simply using CSS to target .views-row-1 differently than the other rows, as Jimajamma mentioned.

However, if you had a situation where the content in that first row was much more different than in the other rows, there is a solution natively in Views to create this sort of layout.

Create two displays in your View using the same filter criteria.  Display A would be a block that shows only one node (the top, larger item in your mockup) and has a larger image format and different order for the fields to be displayed.  Display B would be the display that you use as the page that your users see.  You would attach Display A to the header of Display B and set Display B to be offset by 1 result, so that it does not duplicate the first node.

Here is a screenshot of the Views 3 UI, showing where to find these settings.  Earlier versions of Views support the same type of set-up, but the naming and placement of the settings in the UI is different: https://skitch.com/sheenad/gqdmm/archive-content-shop.