Alternative query to avoid count(distinct)
DISTINCT is always a huge overhead.
You might try to move the aggregation into a Derived Table (of course this might only help if the optimizer is not smart enough to do that automatically)

select dc.Country,
  fvcd.Visitors
from 
 (
   select 
       fvcd.IdCountry,
       COUNT(DISTINCT fvcd.IdAppInstance) AS Visitors
   FROM 
       dbo.Fact_VisitorsCountryDetails fvcd
   WHERE
       fvcd.IdDate BETWEEN @IdMinDate AND @IdMaxDate 
       AND fvcd.IdPartnerid = @IdPartnerId
   GROUP BY
       fvcd.IdCountry
 ) fvcd
INNER JOIN dbo.Dim_Country dc ON dc.Id = fvcd.IdCountry   
ORDER BY
    Visitors DESC;