Is it proper to say that two infinite sets are the "same size" if there is a bijection between them? I get the fact that a set can be called countably infinite if it can be bijected with $\mathbb{N}$, but it feels wrong on many levels to say that they are the same size.
Example: $A=\{x \in \mathbb{N} \mid \exists k\in\mathbb{N}\, (x=2k)\}$ is intuitively smaller than $\mathbb{N}$ because it is $50\%$ in size of $\mathbb{N}$. But it is countably infinite.
 A: Two sets are "the same size" is better said as "two sets have the same cardinality" when there exists a bijection from one to the other. 
But essentially, the "size" of a set is the "cardinality of the set". Better yet, speaking of size, especially when speaking of the size of infinite sets, countable or otherwise, is a question of the cardinality of the sets.
Cardinal arithmetic acts pretty much as we would expect when examining the cardinality/size of finite sets.  But cardinal numbers and cardinal arithmetic, specifically when equating or comparing the cardinality of infinite sets, is not necessarily what we would "expect", intuitively, until you have a firm grasp of what cardinality represents.
For example, the interval/subset of the real numbers given by the interval $(0, 1)$ has the same cardinality ("size") as the set of real numbers! There does, in fact, exist a bijection from the interval $(0, 1)$ to the entire set of real numbers. Here too, it seems very unintuitive to say so, which is why a thorough understanding of what cardinality is (and what it is not) is crucial.

As an aside: you might be interested in this post: A set is infinite if and only if it is equivalent to a proper subset of itself. Here, "equivalent to" means "has the same cardinality as".
A: If you apply an injective function to a set, intuitively the image should be the same size as the original set. Your set is the result of applying the injective function "multiply by 2" to the set $\mathbb N$, so it intuitively ought to be the same size as $\mathbb N$.
But as you point out, intuitively it's smaller, because it's a strict subset.
All this tells you is that intuitive ideas of size that you gather from the finite case cannot all transfer to the infinite case. You have to give up some things that are "obviously true" or "obviously equivalent" because with infinitely many items they aren't anymore.
A: For a different perspective from the other answers: you may be interested in the notion of the (natural) density of a set of natural numbers, which offers an intuitive notion of 'size' that jibes with the idea that there are 'half as many' even numbers as whole numbers — but with the catch that very few sets of interest actually have a non-zero density!  The natural density $d(A)$ is defined as the limit $$\lim_{n\to\infty}\frac{\#\{i:i\leq n \wedge i\in A\}}{n}$$
- that is, intuitively, the limit of the percentage of numbers which are members of $A$, as we consider more and more integers.  It's easy to see that the natural density of the even numbers is $\frac12$, and in general the density of the multiples of $k$ is $\frac1k$, just as you would expect; but with one or two notable exceptions, most other sets of interest that have a density tend to have a density of $0$ (for instance, the primes, or the square numbers) and some sets (for instance, the set of 'numbers with an odd number of $1$s in their binary expansion') have no density at all because the limit doesn't exist.
A: Yes, with a side remark.
There are many ways to measure sizes of infinite sets, depending on the context. The most basic one is cardinality, and two sets have the same cardinality if there is a bijection between them.
If it is clear that "size" means "cardinality" then it is perfectly fine to say that.
Also related:


*

*Is there a way to define the "size" of an infinite set that takes into account "intuitive" differences between sets?

*Why the principle of counting does not match with our common sense

*Comparing the sizes of countable infinite sets

*Why do the rationals, integers and naturals all have the same cardinality?
