Optimised Code for Pulling Taxonomy Posts

Without spending too long thinking about this one I would imagine you could do it with one query.

$store_array = array();

while (have_posts()) : the_post();
    $store_type = // get term id, slug, name from store type taxonomy
    $store_floor = // get term id, slug, name from floor taxonomy
    $store_array[$store_type][$store_floor] = $post->ID;
endwhile;

// run a foreach on your $store_array

From there you could sequentially list your store types and sub-group by floors within it. Post ID will give you option to get_the_title() and get_permalink().

If you needed more detail you could add another dimension to the array.