Most of what I wanted to write has been conveyed in some form by all the previous answers. Nevertheless, I thought I could add some summary and complement.
What constitutes a languages? Well the vocabulary, of course, as you mentioned, but not only. The grammar as well. And at the end, it is a complete mind process that is translated in a way to express oneself.
If you want to get a different feeling that English, you have to think that English sentences and more importantly words are pretty fixed. You rarely get away from the typical
Subject + Verb + Complement
and the nouns as well as the articles or even verbs barely change depending on other words. So you need to introduce all that to reinforce the feeling of strangeness to English speakers.
As the others, I would say that the first step is to know other real-life languages. Which features do they have, and why and so on. But let us introduce some concepts which might get immediate changes to the feeling of your conlang.
Verbs are quite fixed in English, with basically three tenses, and in most, only a change on the third person singular.
Think about Spanish, where every variation within a tense has to be clear enough to omit completely the pronoun as a subject.
[yo] como; [tu] comes; [el/ella] come; [nosotros] comemos; [vosotros] comeis; [ellos] comen
And adding some more variations with tenses: one or more future, one or more present, two-three pasts forms. And different moods. For example, French and Spanish have 4 of them.
That is known from Latin, Russian or German. Depending on the position/function of the nominal group within the sentence, the words change. For example, in German
der Tisch (Nominativ), des Tischs (Genitiv), den Tisch (Akkusativ), or dem Tisch (Dativ) in German.
German is quite simple in this, but from what I know of Russian, they have more cases, and worse, similarly to other slavic languages, they have declination depending on the gender (male/female) of the subject and/or the number.
Japanese and Korean have some forms of declination (I am not sure what's the best word for it) to indicate the politeness, or the level of respect given to the interlocutor.1
Some languages have mutations. This is due to the fact that pronouncing the words as they are can be quite difficult. To get an idea as English speakers, when indicating a possessive form of a plural word, you often omit the second "s". Like
The Smiths' house is the one over there.
The "correct" Smiths's would result in some complex expression. Some languages go further and actually change the letters.
In Breton, kiger (= Butcher) gives ar c'higer or ar gigerez (= the butcher) depending if its a male or a female person.
Position of the verbs
The order of the words may vary. For example, in English, there are many verbs with particles. For example,
make, make out, make up
have completely different meanings. Nevertheless, the verb and its particle tend to stick quite close to each other. This is, for example, not the case in German, where the particle is sent... at the end of the sentence.
making up an excuse on my way to work becomes making an excuse on my way to work up
And this has an effect on conversations. Indeed, the verb is the most important part of most sentences. That is the one which carry the meaning. If you can't grasp the meaning of a sentence until the very end, you are forced to listen to that person until then. Whereas Romance languages speakers tend to interrupt each other much more frequently. Japanese is similar to German for that having their verbs always at the end of the sentence.2
More grammar words
It was mentioned in an earlier answer, but French, Spanish, and other have a much larger variety of determinants and linking words. But to illustrate this concept, I would use Japanese as an illustration.
わたしはアメリカにいきます。I/me-wa USA-ni go = I go to the USA.
They have some particles to indicate the grammatical function taken by what precedes. wa indicates the subject. ni the destination of the verb to go.
The use of such extra words allow Japanese to move nominal groups around. Their function being indicated by the following particle. Other languages do the same. For example, in Breton
Pesked a zebran alies
Alies e tebran pesked
Debrin a ran pesked alies
all mean the same thing (I often eat fish), but the order of the words is moved around. The main idea, is that the emphasis is placed upon the first group. So depending on the intention of the locutor, the whole sentence looks pretty different.
All those are somewhat simple rules from real languages that could be included to make the sentence sound less English.
1: Most languages I know have some form of politeness in it. But contrary to, e.g., Japanese and Korean, they merely choose a different subject and do not change much more than that. Yet English lost that distinction with the now deceased thou/...
2: In German composed modals, or composed tenses also send more than just the particle at the end of the sentence.