ORDER BY 부분범위로 LIMIT 부터 수행하고 조인하면 문제 없을 텐데
조인부터 수행한 뒤 전체범위로 ORDER BY, LIMIT 하는 모양이네요.
LIMIT 부터 수행하도록 변경해 보세요.

SELECT s_id, s_name, s_name_eng, s_open_time, s_tel, s_comment_title, s_comment, s_charge_range, s_status
     , g1.g_id AS g1_id, g1.g_name_eng AS g1_name_eng, g1.g_img_01 AS g1_img, g1.g_img_alt AS g1_alt
     , g2.g_id AS g2_id, g2.g_name_eng AS g2_name_eng, g2.g_img_01 AS g2_img, g2.g_img_alt AS g2_alt
     , g3.g_id AS g3_id, g3.g_name_eng AS g3_name_eng, g3.g_img_01 AS g3_img, g3.g_img_alt AS g3_alt
     , (SELECT m_val FROM mst_option WHERE m_type = 'SHOP_TYPE' AND m_key = s_type) AS s_type_name
     , (SELECT ad_name FROM mst_area_detail WHERE ad_id = s_area_detail_id) AS s_area_detail_name
  FROM (SELECT s_id, s_name, s_name_eng, s_open_time, s_tel, s_comment_title, s_comment, s_charge_range, s_status
             , s_type, s_area_detail_id
          FROM shop_info
         WHERE s_area_id = '101'
           AND s_start_ymd <= '2016-10-12'
           AND s_end_ymd   >= '2016-10-12'
         ORDER BY s_status DESC, s_update_date DESC
         LIMIT 0, 20
        ) s
  LEFT OUTER JOIN girl_info g1 ON g1.g_s_id = s_id AND g1.g_rank = 1
  LEFT OUTER JOIN girl_info g2 ON g2.g_s_id = s_id AND g2.g_rank = 2
  LEFT OUTER JOIN girl_info g3 ON g3.g_s_id = s_id AND g3.g_rank = 3
 ORDER BY s_status DESC, s_update_date DESC
;

감사합니다!
속도가 많이 줄긴 했는데
(기존 33초정도 -> 4초 정도)

left outer join이 1개 들어갈때 마다 1초씩 늘어나네요..;

기본 테이블 구성이 잘못이 된건지.....
조금더 고민을 해봐야 할듯네요!!

감사합니다!

조인 때문에 느려진다면?
적절한 인덱스가 없다는 거죠.
 - girl_info(g_s_id, g_rank)
서브쿼리 쪽에도 인덱스가 적절한지 확인해 보세요.
 - mst_option(m_type, m_key)
 - mst_area_detail(ad_id)
메인쿼리도 확인
 - shop_info(s_area_id, s_end_ymd, s_start_ymd)