I have just finished writing my first wordpress plugin. It is called LJ Random or Recent and it adds a widget that allows you to replace the Recent Posts widget with a little more functionality.
You can specify to show either Random Posts or Recent Posts depending on the type of page (ie, Single Post, Page, Category, Tag).
The plugin is currently awaiting approval over at wordpress.org, but hopefully it will appear in the plugin directory very shortly.
You can download it from here in the mean time.
Check it out LJ Random Or Recent