Pagination difficulty using custom query in genesis-based custom theme

I’m not familiar with Genesis, but most WordPress pagination issues have similar cause. When you load a page in WordPress, the results of the main default query determines the number of available pages. You’re seeing the results of your custom query, but the pagination is based on an entirely different query. This is typically solved by using the pre_get_posts action to modify the main query rather than run a new query:

function wpa_category( $query ) {
    if ( $query->is_category( 'faculty' ) && $query->is_main_query() ) {
        $query->set( 'posts_per_page', 4 );
        $query->set( 'orderby', 'rand' );
    }
}
add_action( 'pre_get_posts', 'wpa_category' );

This won’t entirely solve your issues though- the random order thing will pop up here as well. The problem is that the order isn’t maintained across multiple pages, it’s randomized for each page load. See this answer for a technique to maintain randomized order across multiple pages.