Assuming you're using the single index I suggested, you could accept a search of CityId=@CityId from the user, but to force the query to use theindex you would always add a date filter first - in this case all dates. So:

WHERE Date BETWEEN '01 Jan 1980' AND GETDATE() AND CityId = @CityId

...assuming all you dates are later than Jan 1980