more of this:
...
FAIL: gdb.linespec/cpls-ops.exp: ops-valid-unique: no-whitespace: tab complete "b test_op_NEQ::operator!=(E" (clearing input line) (timeout)
FAIL: gdb.linespec/cpls-ops.exp: ops-valid-unique: no-whitespace: cmd complete "b test_op_NEQ::operator!=(E"
...

And more of this, with "taskset -c 0":
...
FAIL: gdb.base/options.exp: cmd=require-delimiter: test-misc: tab complete "maint test-options require-delimiter -" (clearing input line) (timeout)
FAIL: gdb.base/options.exp: cmd=require-delimiter: test-misc: cmd complete "maint test-options require-delimiter -"

FAIL: gdb.base/options.exp: test-frame-apply: tab complete "frame apply level 0-" (clearing input line) (timeout)
FAIL: gdb.base/options.exp: test-frame-apply: cmd complete "frame apply level 0-"

FAIL: gdb.linespec/explicit.exp: complete with no arguments and no symbols: tab complete "b -" (clearing input line) (timeout)
FAIL: gdb.linespec/explicit.exp: complete with no arguments and no symbols: cmd complete "b -"
...

I regularly get this on my CI, tried to look into it, but couldn't find any clue...

Is it a problem of too much going on and GDB/dejagnu not being able to cope with it?

I minimized to:
...
$ cat gdb/testsuite/gdb.gdb/unittest.exp
set bell_re "\\\x07"

set n 1000
for {set i 0} {$i < $n} {incr i} {
    with_test_prefix $i {
        clean_restart

        set cmd "maintenance selftest name_that_does_not_exist"

        set test "test_completion: tab complete \"$cmd\""

        send_gdb "$cmd\t"

        gdb_test_multiple "" "$test" {
            -re "$cmd$bell_re$" {
                pass $gdb_test_name
            }
        }

        send_gdb "\003"

        gdb_test_multiple "" "$test (clearing input line)" {
            -re "Quit\r\n$gdb_prompt $" {
            }
        }

        send_gdb "\n"
        gdb_test_multiple "" "$test (enter)" {
            -re "\r\n$gdb_prompt $" {
            }
        }
    }
}
...
and am able to reproduce the FAIL by running the test-case with taskset -c 0.

I added the "\n" bit to get an idea of what happens after the timeout, and got:
...
(gdb) maintenance selftest name_that_does_not_exist^GPASS: gdb.gdb/unittest.exp: 59: test_completion: tab complete "maintenance selftest name_that_does_not_exist"
FAIL: gdb.gdb/unittest.exp: 59: test_completion: tab complete "maintenance selftest name_that_does_not_exist" (clearing input line) (timeout)
^C^M
Ran 0 unit tests, 0 failed^M
(gdb) Quit^M
(gdb) 
...

This seems like what would happen if we'd first do \n, and then ^C.

AFAICT, the terminal echoes first ^C, then the \n, so at least there the order seems correct.

With set debug event-loop all, we have passing case:
...
(gdb) set debug event-loop all^M
(gdb) PASS: gdb.gdb/unittest.exp: 60: set debug event-loop all
[event-loop] handle_file_event: invoking fd file handler `ui-1`^M
maintenance selftest name_that_does_not_exist^GPASS: gdb.gdb/unittest.exp: 60: test_completion: tab complete "maintenance selftest name_that_does_not_exist"
[event-loop] mark_async_signal_handler: markingasync signal handler `sigint`^M
[event-loop] invoke_async_signal_handlers: invoking async signal handler `sigint`^M
Quit^M
(gdb) [event-loop] handle_file_event: invoking fd file handler `ui-1`^M
^M
(gdb) 
...
vs failing case:
...
(gdb) set debug event-loop all^M
(gdb) PASS: gdb.gdb/unittest.exp: 61: set debug event-loop all
[event-loop] handle_file_event: invoking fd file handler `ui-1`^M
maintenance selftest name_that_does_not_exist^GPASS: gdb.gdb/unittest.exp: 61: test_completion: tab complete "maintenance selftest name_that_does_not_exist"
FAIL: gdb.gdb/unittest.exp: 61: test_completion: tab complete "maintenance selftest name_that_does_not_exist" (clearing input line) (timeout)
[event-loop] handle_file_event: invoking fd file handler `ui-1`^M
^C[event-loop] mark_async_signal_handler: markingasync signal handler `sigint`^M
^M
Ran 0 unit tests, 0 failed^M
(gdb) [event-loop] invoke_async_signal_handlers: invoking async signal handler `sigint`^M
Quit^M
(gdb) 
...

By using with_timeout_factor 1000, we can attach to gdb, and investigate what's going on.  And we have:
...
(gdb) p _rl_caught_signal
$2 = 2
...

I added this to capture the moment when the SIGINT is caught:
...
diff --git a/readline/readline/signals.c b/readline/readline/signals.c
index 8fedc370a1a..dffd66ae553 100644
--- a/readline/readline/signals.c
+++ b/readline/readline/signals.c
@@ -166,6 +166,7 @@ _rl_signal_handler (int sig)
 static RETSIGTYPE
 rl_signal_handler (int sig)
 {
+  __builtin_abort ();
   _rl_caught_signal = sig;
   SIGHANDLER_RETURN;
 }
...

Backtrace of corresponding core file:
...
(gdb) bt
#0  raise (sig=6) at ../sysdeps/unix/sysv/linux/raise.c:51
#1  0x00000000007606b6 in handle_fatal_signal (sig=6)
    at gdb/event-top.c:971
#2  <signal handler called>
#3  __GI_raise (sig=6) at ../sysdeps/unix/sysv/linux/raise.c:51
#4  0x00007ffa99911375 in __GI_abort () at abort.c:79
#5  0x0000000000ce4336 in rl_signal_handler (sig=2)
    at readline/readline/signals.c:169
#6  <signal handler called>
#7  0x0000000000ce0f1a in update_line (
    old=0x3897050 "(gdb) maintenance selftest name_that_does_not_exist", 
    old_face=0x389f060 '0' <repeats 51 times>, 
    new=0x38a7070 "(gdb) maintenance selftest name_that_does_not_exist", 
    new_face=0x38af080 '0' <repeats 51 times>, current_line=0, omax=32766, nmax=32766, 
    inv_botlin=0) at readline/readline/display.c:1938
#8  0x0000000000cdfd6b in rl_redisplay ()
    at readline/readline/display.c:1518
#9  0x0000000000cc87dd in _rl_internal_char_cleanup ()
    at readline/readline/readline.c:533
#10 0x0000000000cc8b24 in readline_internal_char ()
    at readline/readline/readline.c:681
#11 0x0000000000ce8c63 in rl_callback_read_char ()
    at readline/readline/callback.c:264
#12 0x000000000075f4a0 in gdb_rl_callback_read_char_wrapper_noexcept ()
    at gdb/event-top.c:188
#13 0x000000000075f527 in gdb_rl_callback_read_char_wrapper (client_data=0x3537150)
    at gdb/event-top.c:205
#14 0x000000000075fc74 in stdin_event_handler (error=0, client_data=0x3537150)
    at gdb/event-top.c:525
#15 0x00000000013a9b60 in handle_file_event (file_ptr=0x37e4490, ready_mask=1)
    at gdbsupport/event-loop.cc:574
#16 0x00000000013aa0e8 in gdb_wait_for_event (block=1)
    at gdbsupport/event-loop.cc:695
#17 0x00000000013a8fbc in gdb_do_one_event (mstimeout=-1)
    at gdbsupport/event-loop.cc:265
#18 0x00000000008a65b3 in start_event_loop ()
    at gdb/main.c:411
#19 0x00000000008a66d3 in captured_command_loop ()
    at gdb/main.c:471
#20 0x00000000008a7eeb in captured_main (data=0x7ffff205b580)
    at gdb/main.c:1330
#21 0x00000000008a7f51 in gdb_main (args=0x7ffff205b580)
    at gdb/main.c:1345
#22 0x000000000041506e in main (argc=9, argv=0x7ffff205b698)
    at gdb/gdb.c:32
(gdb) 
...

Piecing together the information, I see the following scenario:
- expect sends "\t"
- gdb detects the stdin event, and calls rl_callback_read_char
- readline interprets the \t as completion, tries to complete, fails to do so,
  outputs a bell (^G)
- expect sees the bell, and proceeds to send the signal
- readline is still in the call to rl_callback_read_char, and stores the
  signal in _rl_caught_signal
- readline returns from the call to rl_callback_read_char, without having
  handled _rl_caught_signal
- gdb goes to wait for the next event
- expect times out waiting for "Quit"
- expect sends "\n"
- readline now handles both _rl_caught_signal and "\n", but in the opposite
  order

Tentative fix:
...
diff --git a/gdb/event-top.c b/gdb/event-top.c
index 290c3d87744..24c61131b8d 100644
--- a/gdb/event-top.c
+++ b/gdb/event-top.c
@@ -186,6 +186,8 @@ gdb_rl_callback_read_char_wrapper_noexcept () noexcept
   TRY_SJLJ
     {
       rl_callback_read_char ();
+      while (rl_pending_signal () != 0)
+       rl_check_signals ();
       if (after_char_processing_hook)
        (*after_char_processing_hook) ();
     }
...

Submitted RFC: https://sourceware.org/pipermail/gdb-patches/2022-September/191813.html

Committed https://sourceware.org/git/?p=binutils-gdb.git;a=commit;h=faf01aee1d03aef5b6f95fd0db358bf5e70578f9 

Keeping this PR open, because it's only fixed for readline >= 8.0.

Next step: ask upstream readline about this problem: is it a bug in PR? If not, how is this supposed to be addressed in readline < 8.0 ?

*** Bug 29199 has been marked as a duplicate of this bug. ***

In the meanwhile, a fix was committed in the devel branch of the readline repo, contained in commit 8d0c439 ("rollup of changes since readline-8.2"), first proposed here ( https://lists.gnu.org/archive/html/bug-readline/2022-10/msg00008.html ).

Fix proposed for readline 7: https://sourceware.org/pipermail/gdb-patches/2023-May/199802.html

The master branch has been updated by Tom de Vries <vries@sourceware.org>:

https://sourceware.org/git/gitweb.cgi?p=binutils-gdb.git;h=a6bc87757c85035a7cbb44da0706084043af68d1

commit a6bc87757c85035a7cbb44da0706084043af68d1
Author: Tom de Vries <tdevries@suse.de>
Date:   Wed Jun 7 14:57:40 2023 +0200

    [gdb/cli] Handle pending ^C after rl_callback_read_char for readline 7
    
    In commit faf01aee1d0 ("[gdb] Handle pending ^C after rl_callback_read_char")
    we handled a problem (described in detail in that commit) for readline >= 8
    using public readline functions rl_pending_signal and rl_check_signals.
    
    For readline 7 (note that we require at least readline 7 so there's no need to
    worry about readline 6), there was no fix though, because rl_check_signals was
    not available.
    
    Fix this by instead using the private readline function _rl_signal_handler.
    
    There is precedent for using private readline variables and functions, but
    it's something we want to get rid of (PR build/10723).  Nevertheless, I think
    we can allow this specific instance because it's not used when building
    against readline >= 8.
    
    [ In the meanwhile, a fix was committed in the devel branch of the readline
    repo, contained in commit 8d0c439 ("rollup of changes since readline-8.2"),
    first proposed here (
    https://lists.gnu.org/archive/html/bug-readline/2022-10/msg00008.html ). ]
    
    Tested on x86_64-linux, against system readline 7.0 on openSUSE Leap 15.4.
    
    PR cli/27813
    Bug: https://sourceware.org/bugzilla/show_bug.cgi?id=27813

Fixed, now also for readline 7.