The reals and the integers do have different cardinalities, but not for the reason you imply. In fact, the rational numbers have the same cardinality (the same infinity) as the integers, but they have the same property that you use to characterize the reals, i.e., that between any two distinct rationals there is an infinite number of rationals.

One way to see that there are as many integers as there are rational numbers is just to find a way to count the rational numbers. There are a number of ways to do this. There is a very nice and explicit way to do enumerate the positive rationals that involves the prime factorization of the integers. Suppose first that p is a prime number. We identify p^k with the integer p^{2k}. For the rational number 1/p^k (p is still prime), we label it by the integer p^{2k-1}. For a rational number p/q in lowest terms, we take the prime factorization of p and the prime factorization of q, apply the above identification to each factor p_i ^k and then take the product. This gives a very explicit bijection between the positive rationals and the positive integers.with

My favorite way, though, is just to make a grid of pairs of integers (numerator, denominator), and then count them by spiraling outward on the grid. This yields duplicates, but that's ok.