The easiest way to do this would be the List widget included in the Widget Pack. You can set up the List widget to display a list to display as randomized. You can then placed in the theme’s sidebar or placed on a page with a shortcode.
Now, you can also use the Connections shortcode with the order_by shortcode option. There is an example on how to display a randomized list. This setup will be a little more complicated so I highly recommend setting the home_id shortcode option with tht epage ID of the page set as your directory home page. So, your shortcode on the home page would look something like this:
[connections home_id=X order_by='id|RANDOM']
Hope this answers your question thoroughly!