I would say you have to run queries by category name or category ID, use WP_Query:
$query = new WP_Query( 'cat=cat_ID', 'posts_per_page' => 4 );
Maybe get_posts() is more appropriate in this context (array of posts)
EDIT: in your edit use get_the_post_thumbnail( $post->ID, 'thumbnail')instead, small is not a default size
EDIT2: it is better to use the_title_attribute() instead of the_title() if is in an HTML attribute :
title="'.the_title_attribute($post->ID).'"
In case you use quote in your title it will escape it so it won’t break HTML