You have 2 unrelated queries. First, let me discuss a third query (since you provided the data needed to explain it thoroughly):
SELECT * FROM gift gift0_ WHERE gift0_.client_id=24;
Plan A: Walk thru the 1.5M entries in the INDEX for client_id; for each of them reach over into the data (random disk fetch) to find the data.
Plan B: Totally ignore the INDEX; simply go thru the 4M data rows consecutively, filtering out the uninteresting ones as it goes. (You have not provided the number of rows in the table; I made up the 4M for this discussion.)
Plan A has to read a lot of blocks of the index, plus probably all of the data blocks. Furthermore the data blocks are probably scattered around.
Plan B is straightforward, may take advantage of readahead, etc.
Plan B is faster.
Plan B was picked when the optimizer decided that 1.5M was "too big" a percentage of 3.6M.
Face it, doing a query that needs to hit 1.5M rows will take time.
Back to your queries...
I can't tell if client 15 also has "too many" rows.
SELECT count(*) FROM gift gift0_ WHERE gift0_.client_id=24;
says "Using index". That means that the optimizer realized it could do all the work in the index blocks, thereby not hitting the data blocks at all.
It said 3552560 as an estimate; granted, a rather poor estimate. It will examine only 1.5M rows of the index.
SELECT * FROM gift gift0_ WHERE gift0_.client_id=24;
is a different query, with a different EXPLAIN plan. It cannot be "Using index", and runs as I described above.
This are two more situations:
SELECT count(*) FROM gift gift0_ WHERE gift0_.client_id=24 AND ...;
SELECT * FROM gift gift0_ WHERE gift0_.client_id=24 AND ...;
Because of the extra AND, it cannot be "Using index", and it will have to hit 1.5M rows of index _and_ data (unless there is a better index than (client_id)).