Latin would be your best bet in Europe. The general populace wouldn't understand you but you could endear yourself to the clergy with it.

Modern hebrew is somewhat different, but understandable to those that speak biblical hebrew. But I think in those days they did not speak it, but rather spoke aramaic.

I don't know about Hebrew but I bet Arabic would be the language to know in 1000 AD if you were in Spain or Persia or many points in between.

Arabic's a good bet because the Qu'ran is still written in the original Mediaeval Arabic and people learn it in order to read it in its original form. The accent might have changed over time but Arabic's going to be good for any time in the last 1300 years.

Modern Standard Arabic (The generalized approximation of what college-educated people speak nowadays) is fairly different from Koranic Arabic, but it'd still probably be at least somewhat mutually intelligible, so you could pass as being from some other part of the Arab world I suppose.

Spain would've probably been the best possible place to land during the Ummayad/Abbasid Caliphates (before about 1085 or so), but it was a very rough place afterward (the Almoravid/Almohad Caliphates were not known for tolerance, and the reconquest was even worse)

Modern Icelandic is very close to medieval Icelandic as spoken by the Vikings. Apparently, manuscripts of the sagas can be read and interpreted by an Icelandic speaker with no special training, just as you or I could read an original printing of one of Shakespeare's plays.