Which storage scheme is optimal depends very strongly on the access
pattern. You already said that you're accessing them one particle at a
time, but are you going to access the particles sequentially in order,
or randomly? Another conventional name for this issue is
struct-of-arrays vs array-of-structs.
The key thing here is to know how the memory hierarchy works on a CPU
(see, e.g.,
https://www.scss.tcd.ie/Jeremy.Jones/CS3021/5%20caches.pdf, as well as the many questions on this topic on Stack Overflow). Reads
from main memory have a very large latency, which will lead to long
stalls in the execution, unless this is mitigated by prefetching. Each
read from main memory will read one cache line worth of data, placing
it in cache, and the reads from cache are comparatively free.
So for example if you have a matrix $(a_{ij})_{1\leq i,j\leq 3}$,
and it is stored in column-major order in memory as
$$ a_{11}, a_{21}, a_{31}, a_{12}, a_{22}, a_{32}, a_{13}, a_{23},
a_{33}, $$
then reading $a_{11}$ (or any of $a_{11},\ldots,a_{23}$) will place all the eight elements from $a_{11}$ to
$a_{23}$ in cache (assuming correct alignment and a typical 64-byte
cache line and an element size of 8 bytes), making them free to access.
If you have several different arrays, a struct-of-arrays, like
$$ x_{1}, \ldots, \qquad y_{1}, \ldots, \qquad z_{1}, \ldots $$
and you read $x_1, y_1, z_1$, you will effectively read the first
eight elements of each array. If you end up using the next seven
elements immediately, that's fine. If not, then that wasted 7/8 of
your memory bandwidth by reading 24 elements instead of 3, which is inefficient.
If instead you store them as array-of-structs,
$$ x_1, y_1, z_1, x_2, y_2, z_2, \ldots $$
then reading $x_1,y_1,z_1$ will read the first eight elements. If you use those next
elements, there is no great difference, otherwise you waste 5/8 (reading 8 instead of 3) of your memory bandwidth - note this is still better than reading 24 elements as in the previous example.
With nine 8-byte elements, if you know you'll access them
consecutively there should be no big difference either way, as above. If you will
access them in random order, then reading one set of nine elements
will lead to either $9\times 8 = 72$ elements being read from memory (if
stored as struct-of-arrays) or $\lceil \frac{9}{8}\rceil\times 8 = 16$
elements (if stored as array-of-structs) - this could be a
very large performance gain.
The difference between column-major and row-major, I feel, is a bit of
red herring here - the key is knowing the access pattern, and making
sure the data layout matches the access pattern. The next most
important thing would be prefetching, which is a technique for
hiding the relatively large memory access latency.
A separate related issue to consider is how you access data that you already read previously, and whether it is likely to still remain in the cache or whether it was purged to make way for other data, causing cache misses - an array of $5000\times 9\times 8$ bytes is $360\,\mathrm{KB}$ and will likely fit entirely in either the L2 or L3 cache.
It gets even more complicated if your program involves multiple threads running on different cores, with potentially separate lower-level caches per core.
Note, incidentally, that for non-sequential access patterns, having nine elements per particle is somewhat inefficient in itself if a cache line is 8 elements long as reading nine elements would be essentially equivalent to reading 16 elements - one technique is to split your data into often-used versus rarely-used parts so that the often-used parts fit better.
There is no penalty for having either many rows or columns. Not sure what you mean by a penalty for "many memory addresses", but there is no such penalty.
Some of the things I said depend on exact properties of the architecture your program will run on. Using an interpreted language like R or Matlab can also affect this severely - for C++ it should hold.
In general, it is best to use the array-of-structs pattern, unless you have some specific reasons not to.
